AOJ 1170: 古い記憶

何かAOJ-ICPCの高難度を解くのが流行ってるらしいので流行にのる。

Aho-Corasickで判定はできるんだけど、全部を一つ一つ列挙していると間に合わないので、変な順番で枝刈り探索する。
うーんなんか微妙な問題……

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<vector>
#include<string.h>
using namespace std;
char str[50];
char word[35][30];
vector<string>ans;
struct wolf{
	int flag;
	int par;
	int chi[27];
	int dep;
	int val;
	int fail;
	wolf(){
		flag=dep=0;
		val=-1;
		par=-1;
		fail=0;
		for(int i=0;i<27;i++)chi[i]=-1;
	}
};
int LIM=5;
wolf pool[1100];
typedef unsigned long long nt;
nt key=1000000007;
set<nt>hash;
int len;
int sz;
int ret;
inline int chk(string t,int lc){
	int at=0;
	int last=0;
	for(int i=0;i<t.size();i++){
		while(1){
			if(pool[at].chi[t[i]-'@']!=-1){
				at=pool[at].chi[t[i]-'@'];
				break;
			}
			if(at==0){
				break;
			}
			at=pool[at].fail;
		}
		if(pool[at].flag)last=i+1;
		if(pool[at].dep<=i-last)return 0;
	}
	
	if(lc==0||last==t.size()){
	//	printf("%s\n",t.c_str());
		return 1;
	}
	return 0;
}
void dfs(int a,int b,string now,nt val,nt ks){
	if(chk(now,0)==0)return;
	if(a==len){
		if(hash.count(val)==0){
			hash.insert(val);
			if(chk(now,1)){
				ret++;
				if(ans.size()<LIM){
					ans.push_back(now);
				}
			}
		}
	}
	if(a<len){
		now.push_back(str[a]);
		dfs(a+1,b,now,val+ks*(str[a]-'@'+1),ks*key);
		now.erase(now.size()-1);
		if(b){
			dfs(a+1,b-1,now,val,ks);
			for(int i=0;i<27;i++){
				now.push_back('@'+i);
				dfs(a+1,b-1,now,val+ks*(i+1),ks*key);
				now.erase(now.size()-1);
			}
		}
	}
	if(b){
		for(int i=0;i<27;i++){
			now.push_back('@'+i);
			dfs(a,b-1,now,val+ks*(i+1),ks*key);
			now.erase(now.size()-1);
		}
	}
}

int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),b){
		scanf("%s",str);
		for(int i=0;str[i];i++)if(str[i]=='.')str[i]='@';
		for(int i=0;i<b;i++){
			scanf("%s",word+i);
			for(int j=0;word[i][j];j++)if(word[i][j]=='.')word[i][j]='@';
		}
		ans.clear();
		len=strlen(str);
		ret=0;
		sz=1;
		pool[0]=wolf();
		hash.clear();
		for(int i=0;i<b;i++){
			int at=0;
			for(int j=0;word[i][j];j++){
				if(pool[at].chi[word[i][j]-'@']==-1){
					pool[sz]=wolf();
					pool[sz].val=word[i][j]-'@';
					pool[sz].par=at;
					pool[at].chi[word[i][j]-'@']=sz;
					pool[sz].dep=j+1;
					at=sz;
					sz++;
				}else{
					at=pool[at].chi[word[i][j]-'@'];
				}
			}
			pool[at].flag=1;
		}
		
		queue<int>Q;
		Q.push(0);
		while(Q.size()){
			int now=Q.front();Q.pop();
			for(int i=0;i<27;i++){
				if(~pool[now].chi[i])Q.push(pool[now].chi[i]);
			}
			if(now==0||pool[now].par==0){
				pool[now].fail=0;continue;
			}
			int at=pool[now].par;
			while(1){
				if(at==0){
					pool[now].fail=0;break;
				}
				at=pool[at].fail;
				if(pool[at].chi[pool[now].val]!=-1){
					pool[now].fail=pool[at].chi[pool[now].val];
					if(pool[pool[now].fail].flag)pool[now].flag=1;
					break;
				}
			}
		}
		string T=str;
		dfs(0,a,"",0,1);
		printf("%d\n",ret);
		if(ret<=LIM){
			std::sort(ans.begin(),ans.end());
			for(int i=0;i<ret;i++){
				for(int j=0;j<ans[i].size();j++){
					if(ans[i][j]=='@')printf(".");
					else printf("%c",ans[i][j]);
				}
				printf("\n");
			}
		}
	}
}