Findstrなのです

#include<cstdio>
#include<cstring>
const int maxm=26, maxn=101000;

struct node{
	int par, val;
	int go[maxm];
};
node sam[maxn*2];
int sn;
int root,last;
char read[maxn];
int number[maxn];

struct yjq{
	int f, t, n;
};
yjq naive[maxn<<2];
int nn, pre[maxn<<1], fst[maxn<<1];

bool end[maxn<<1];

void addedge(int f, int t)
{
	nn++;
	naive[nn].f=f;
	naive[nn].t=t;
	if (fst[f])	
		naive[pre[f]].n=nn;
	else
		fst[f]=nn;
	pre[f]=nn;
}

void extend(int now)
{
	sn++;
	sam[sn].val=sam[last].val+1;
	int p=last;
	int np=sn;
	for (; p&&(!sam[p].go[now]); p=sam[p].par)
		sam[p].go[now]=np;
	if (!p)
		sam[np].par=root;
	else
	{
		int q=sam[p].go[now];
		if (sam[q].val==sam[p].val+1)
			sam[np].par=q;
		else
		{
			int nq=++sn;
			sam[nq].val=sam[p].val+1;
			memcpy(sam[nq].go,sam[q].go,sizeof sam[q].go);
			sam[nq].par=sam[q].par;
			sam[q].par=nq;
			sam[np].par=nq;
			for (; p&&sam[p].go[now]==q; p=sam[p].par)
			{
				sam[p].go[now]=nq;
			}
		}
	}
	last=np;
}

void walk_sam(int nowp)
{
	for (int c=0; c<maxm; c++)
	{
		if (sam[nowp].go[c])
		{
			printf("%d --%c-> %d\n",nowp,c+'a',sam[nowp].go[c]);
		}
	}
}

int main()
{
	scanf("%s",read+1);
	int n=strlen(read+1);
	root=last=1;
	sn=1;
	for (int i=1; i<=n; i++)
	{
		number[i]=read[i]-'a';
		extend(number[i]);
	}
	for (int i=root; i<=sn; i++)
		addedge(sam[i].par,i);
	dfs(root);
	return 0;
}