字符串ACM模板.doc

<字符串>
KMP
#include<iostream>
usingnamespacestd;
chart[10010],s[1000100];
intkmpNext[10010];
/*standardCcodeforKMP*/
voidpreKmp(char*x,intm,intkmpNext[])
{
inti,j;

i=0;
j=kmpNext[0]=-1;
while(i<m)
{
while(j>-1&&x[i]!=x[j])
{
j=kmpNext[j];
}

i++;
j++;

if(x[i]==x[j])
{
kmpNext[i]=kmpNext[j];
}
else
{
kmpNext[i]=j;
}
}
}
intKMP(char*x,intm,char*y,intn)
{
inti,j,tot=0;

/*Preprocessing*/
preKmp(x,m,kmpNext);

/*Searching*/
i=j=0;
while(j<n)
{
while(i>-1&&x[i]!=y[j])
{
i=kmpNext[i];
}

i++;
j++;
if(i>=m)
{
//OUTPUT(j-i);
/*foundone,donextifrequired*/
tot++;
i=kmpNext[i];
}
}
returntot;
}
intmain()
{
intT;
//freopen("in.txt","r",stdin);
scanf("%d\n",&T);
while(T--)
{
gets(t);
gets(s);
printf("%d\n",KMP(t,strlen(t),s,strlen(s)));
}
return0;
}

通配符匹配
intwildcard(constchar*pat,constchar*str)
{
while(*str&&*pat)
{
if(*pat=='?')
{
if(wildcard(pat+1,str+1))return1;
str++;
pat++;
}
elseif(*pat=='*')
{
while(*pat=='*')pat++;
if(!*pat)return1;

while(*str)
{
if(wildcard(pat,str))return1;
str++;
}
return0;
}
else
{
if(*pat!=*str)return0;
str++;
pat++;
}
}

if(*str!=0)return0;

while(*pat=='*')pat++;
return!*pat;
}

最小表示法
说把一个长为len的字符串围成一个圈，然后从任意一个字符作为起点顺时针转，都会产生一个新的长为len字符串，现在要求所有的可以产生的字符串中字典序最小的那个。下面这个函数就是解决这个问题的，返回值即为从原串中这个位置起产生的串就是字典序最小的。

intMinimumRepresentation(char*s,intl)
{
inti=0,j=1,k=0,t;
while(i<l&&j<l&&k<l)
{
t=s[(i+k)%l]-s[(j+k)%l];
if(!t)++k;
else
{
if(t>0)i=i+k+1;
elsej=j+k+1;
if(i==j)++j;
k=0;
}
}
returnmin(i,j);
}

后缀数组倍增算法
#include<stdio.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
usingnamespacestd;
#defineMAX200010

intSA[MAX],Rank[MAX],lstRank[MAX];
intheight[MAX];
charstr[MAX];
intpower,n;

boolcmpList(constint&a,constint&b)
{
returnlstRank[a]<lstRank[b]
||lstRank[a]==lstRank[b]&&lstRank[a+power]<lstRank[b+power];
}

boolcmpChar(constint&a,constint&b)
{
returnstr[a]<str[b];
}

voidsuffixArray()
{
inti,j;
for(i=0;i<n;i++)SA[i]=i;
sort(SA,SA+n,cmpChar);
for(i=0,j=0;i<n;i++){
if(i>0&&str[SA[i]]!=str[SA[i-1]])j++;
Rank[SA[i]]=j;
}