KMP+TRIE

int val[1000100][31],tot;

int tr[1000100];

int fail[1000100];

struct AC_Trie{

	void clean(){

		tot=0;

		memset(val,0,sizeof(val));

		memset(tr,0,sizeof(tr));

		memset(fail,0,sizeof(fail));

	}

	void build(){

		queue<int> q;

		memset(fail,0,sizeof(fail));

		while(!q.empty()) q.pop();

		for(int i=0;i<26;i++) if(val[0][i]!=0) q.push(val[0][i]);

		while(!q.empty()){

			int u=q.front();q.pop();

			for(int i=0;i<26;i++){

				if(val[u][i]!=0){

					fail[val[u][i]]=val[fail[u]][i];

					q.push(val[u][i]);

				}else{

					val[u][i]=val[fail[u]][i];

				}

			}

		}

	}

	void insert(string x){

		int len=x.length(),p=0;

		for(int i=0;i<len;i++){

			int c=x[i]-'a';

			if(val[p][c]==0) tot++,val[p][c]=tot;

			p=val[p][c];

		}

		tr[p]++;

	}

	int find(string x){

		int len=x.length(),p=0,res=0;

		for(int i=0;i<len;i++){

			p=val[p][x[i]-'a'];

			for(int j=p;j&&~tr[j];j=fail[j]) res+=tr[j],tr[j]=-1;

		}

		return res;

	}

}tree;