子串的個數（慘遭水題無情吊打！！！）

子串的個數

給你一個由小寫字母“a,b,c,d,e”構成的字元串S，請找出S中包含了多少個不同的長度為N的子串。例如，給出的字元串是"daababac"，N的值為3，那麼長度為3的不同子串有"daa"; "aab"; "aba"; "bab"; "bac"，最後輸出的結果是5。

一開始給你一個空字元串S,有兩個操作需要你完成：

編号“1”：在S後添加一個字元串S’,(也就是字元串加法S=S+S’)；

編号“2”：輸出目前S中包含的不相同的長度為N的字元串的個數；

輸入格式：

第一行，一個整數N

第二行，一個整數M，表示下面有M個操作

接下來M行，每行表示一個操作（1号操作為數字1，然後是一個空格，接着是一個字元串，2号操作隻有一個數字2）。

輸出格式：

對于每個編号2的操作，輸出一整數，表示所求結果。

樣例輸入1：	樣例輸入2：
3 4 1 daababac 2 1 acc 2	4 5 1 ebaedabedaedbaedaedbaedbaeadeaccccccc 1 ddddd 2  1 abcd 2
樣例輸出1:	樣例輸出2:
5 8	24 28

資料範圍:

對于  50% 的資料：1≤M≤100    1≤字元串S最終的長度≤10,000    1≤N≤8

對于 100% 的資料：1≤M≤1000   1≤字元串S最終的長度≤200,000   1≤N≤8

—————————————————————————————————————————————————————————————————————————————

這道題有很多種解法，簡記一下。

1.trie樹；

=========================

這是一顆神奇的樹！

注意從原點0 開始，漫漫坑跌路，被坑了幾次了！

但毫無疑問，這是最快的。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
struct node{int s[5];};
node trie[200005];
char B[200005],A[200005];
int n,m,now,cnt,tot;

void insert(char a[10])
{
	int i,p=0;
	bool mark=0;
	for(i=1;i<=n;i++)
	{
		int t=a[i]-'a';
		if(trie[p].s[t])p=trie[p].s[t];
		else
		{
			tot++;mark=1;
			p=trie[p].s[t]=tot;
		}
	}
	if(mark)cnt++;
}
int main()
{
//	freopen("data7.in","r",stdin);
//	freopen("data.out","w",stdout);
	int i,j,k,t,p=1,q,l;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d",&k);
		if(k==1)
		{
			scanf("%s",A+1);
			A[0]=' ';
			l=strlen(A)-1;
			q=1;
			while(q<=l)
			{
				for(j=p;j<=n;j++)
				{
					B[j]=A[q++];
//				printf("-%c-",B[j]);
				}
//				for(j=1;j<=n;j++)printf("-%c-",B[j]);
//				putchar(10);
				B[0]=' ';
//				for(j=1;j<=n;j++)printf("%c",B[j]);
				if(j==n+1)
				{
					insert(B);
					for(j=1;j<n;j++)B[j]=B[j+1];
					p=n;
				}
			}
		}
		if(k==2)printf("%d\n",cnt);
	}
//	system("pause");
	return 0;
}
           

2.hash；

=========================

我的hash寫的很渣。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
string a="",b,s;
bool mark[17000000];
unsigned int hash(string s)
{
	unsigned int hash=0,seed=131;
	unsigned int i=0,len=s.length();
	while(i<len)hash=hash*seed+s[i++];
	return (hash&0xFFFFFF);
}
int main()
{
	int n,m,j,len,k,t,tot=0,i;
	scanf("%d%d",&n,&m);
	len=n-1;
	for(i=1;i<=m;i++)
	{
		scanf("%d",&k);
		if(k==1)
		{
			cin>>b;
			a+=b;
			for(j=len-n+1,len=a.length();j+n<=len;j++)
			{
				s=a.substr(j,n);
				t=hash(s);
				if(!mark[t])
				{
					tot++;
					mark[t]=1;
				}
			}
		}
		else printf("%d\n",tot);
	}
//	system("pause");
	return 0;
}
           

3.神奇的map；

=========================

萬萬沒想到，唉，to young to simple；

但事實告訴我們，手寫的确實要快一些。

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
map<string,int>mp;
string a="",b;
int main()
{
	int n,m,i,j,len,k;
	scanf("%d%d",&n,&m);
	len=n-1;
	for(i=1;i<=m;i++)
	{
		scanf("%d",&k);
		if(k==1)
		{
			cin>>b;
			a+=b;
			for(j=len-n+1,len=a.length();j+n<=len;j++)
			mp[a.substr(j,n)]++;
		}
		else printf("%d\n",mp.size());
	}
	return 0;
}      

4.更神奇的5進制；

這不給我說，打死都想不到。

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
bool mark[500000];
int Mod[]={1,5,25,125,625,3125,15625,78125,390625};
string a="",b,s;
int n;
int change(string s)
{
	int tot=0;
	for(int i=0;i<n;i++)tot+=(s[i]-'a')*Mod[i];
	return tot;
}
int main()
{
	int k,m,i,j,len,t,tot=0;
	scanf("%d%d",&n,&m);
	len=n-1;
	for(i=1;i<=m;i++)
	{
		scanf("%d",&k);
		if(k==1)
		{
			cin>>b;
			a+=b;
			for(j=len-n+1,len=a.length();j+n<=len;j++)
			{
				s=a.substr(j,n);
				t=change(s);
				if(!mark[t])
				{
					tot++;
					mark[t]=1;
				}
			}
		}
		else printf("%d\n",tot);
	}
	return 0;
}      

（完）