C++解答

#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <math.h>
#include <map>
#include <algorithm>
using namespace std;

inline int input(){
	int ret=0;bool isN=0;char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') isN=1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		ret=ret*10+c-'0';
		c=getchar();
	}
	return isN?-ret:ret;
}

#define clr(a) memset(a,-1,sizeof(a))
#define rep(i,s,t) for(int i=s;i<t;i++)
#define Maxn 1000

struct SA_node{
	int len,pre,next[26];
	void init(){
		pre=-1;len=0;clr(next);
	}
}root[Maxn<<1];
int tot,last,p,q,nxt;

inline void extend(int w){
	p=last;last=tot++;
	root[last].init();
	root[last].len=root[p].len+1;
	while(p!=-1 && root[p].next[w]==-1){
		root[p].next[w]=last;
		p=root[p].pre;
	}
	if(p==-1){
		root[last].pre=0;
		return;
	}
	q=root[p].next[w];
	if(root[p].len+1 == root[q].len){
		root[last].pre=q;
		return;
	}
	nxt = tot++;
	root[nxt].len=root[p].len+1;
	root[nxt].pre=root[q].pre;
	memcpy(root[nxt].next,root[q].next,sizeof(root[q].next));
	root[last].pre=root[q].pre=nxt;
	while(p!=-1 && root[p].next[w]==q){
		root[p].next[w]=nxt;
		p=root[p].pre;
	} 
}

inline void dfs(int p,int *a,int l){
	if(l>=1){
		rep(i,0,l){
			printf("%c",'a'+a[i]);
		}
		printf("\n");
	}
	rep(i,0,26){
		if(root[p].next[i]!=-1){
			a[l]=i;
			dfs(root[p].next[i],a,l+1);
		}
	}
}

int t;
int a[1005];
char s[1005];
int main(){
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
	t=input();
	while(t--){
		scanf("%s",s);int l=strlen(s);
		tot=last=0;
		root[tot++].init();
		rep(i,0,l) extend(s[i]-'a');
		dfs(0,a,0);
	}
	return 0;
}