上海大学 ACM 模板 by kuangbin
while(-1!=j && x[i]!=x[j])j=kmpNext[j];
if(x[++i]==x[++j])kmpNext[i]=kmpNext[j];
else kmpNext[i]=j;
}
}
/*
* 返回x在y中出现的次数,可以重叠
*/
int next[10010];
int KMP_Count(char x[],int m,char y[],int n)
{//x是模式串,y是主串
int i,j;
int ans=0;
//preKMP(x,m,next);
kmp_pre(x,m,next);
i=j=0;
while(i
=m)
{
}
ans++;
j=next[j];
return ans;
}
经典题目:POJ 3167
/*
* POJ 3167 Cow Patterns
* 模式串可以浮动的模式匹配问题
* 给出模式串的相对大小,需要找出模式串匹配次数和位置
* 比如说模式串:1,4,4,2,3,1 而主串:5,6,2,10,10,7,3,2,9
* 那么2,10,10,7,3,2就是匹配的
*
* 统计比当前数小,和于当前数相等的,然后进行kmp
*/
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=100010;
const int MAXM=25010;
int a[MAXN];
int b[MAXN];
int n,m,s;
int as[MAXN][30];
int bs[MAXM][30];
void init()
for(int i=0;i上海大学 ACM 模板 by kuangbin
if(i==0)
{
}
for(int j=1;j<=25;j++)as[i][j]=0;
else
{
}
for(int j=1;j<=25;j++)as[i][j]=as[i-1][j];
as[i][a[i]]++;
}
for(int i=0;i0)t11+=bs[i][k]-bs[i-j-1][k];
else t11+=bs[i][k];
if(i-j>0)t12=bs[i][b[i]]-bs[i-j-1][b[i]];
else t12=bs[i][b[i]];
for(int k=1;kans;
void kmp()
ans.clear();
int i,j;
kmp_pre();
{
4 / 173
ACM 模板
kuangbin
上海大学 ACM 模板 by kuangbin
i=j=0;
while(i
0)t11+=as[i][k]-as[i-j-1][k];
else t11+=as[i][k];
if(i-j>0)t12=as[i][a[i]]-as[i-j-1][a[i]];
else t12=as[i][a[i]];
for(int k=1;k=m)
{
}
ans.push_back(i-m+1);
j=next[j];
else j=next[j];
}
}
int main()
{
while(scanf("%d%d%d",&n,&m,&s)==3)
{
for(int i=0;i上海大学 ACM 模板 by kuangbin
//extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀
void pre_EKMP(char x[],int m,int next[])
{
}
next[0]=m;
int j=0;
while(j+1
上海大学 ACM 模板 by kuangbin
Ma[l++]='#';
for(int i=0;i
i?min(Mp[2*id-i],mx-i):1;
while(Ma[i+Mp[i]]==Ma[i-Mp[i]])Mp[i]++;
if(i+Mp[i]>mx)
{
}
mx=i+Mp[i];
id=i;
}
/*
* abaaba
* i: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
* Ma[i]: $ # a # b # a # a $ b # a #
* Mp[i]: 1 1 2 1 4 1 2 7 2 1 4 1 2 1
*/
char s[MAXN];
int main()
{
}
while(scanf("%s",s)==1)
{
}
int len=strlen(s);
Manacher(s,len);
int ans=0;
for(int i=0;i<2*len+2;i++)
ans=max(ans,Mp[i]-1);
printf("%d\n",ans);
return 0;
4、AC 自动机
//======================
// HDU 2222
// 求目标串中出现了几个模式串
//====================
#include
#include
#include
#include
#include
using namespace std;
struct Trie
{
int next[500010][26],fail[500010],end[500010];
7 / 173
ACM 模板
kuangbin
上海大学 ACM 模板 by kuangbin
int root,L;
int newnode()
{
}
for(int i = 0;i < 26;i++)
next[L][i] = -1;
end[L++] = 0;
return L-1;
void init()
{
}
L = 0;
root = newnode();
void insert(char buf[])
{
}
int len = strlen(buf);
int now = root;
for(int i = 0;i < len;i++)
{
}
if(next[now][buf[i]-'a'] == -1)
next[now][buf[i]-'a'] = newnode();
now = next[now][buf[i]-'a'];
end[now]++;
void build()
{
queueQ;
fail[root] = root;
for(int i = 0;i < 26;i++)
if(next[root][i] == -1)
next[root][i] = root;
else
{
}
fail[next[root][i]] = root;
Q.push(next[root][i]);
while( !Q.empty() )
{
}
int now = Q.front();
Q.pop();
for(int i = 0;i < 26;i++)
if(next[now][i] == -1)
next[now][i] = next[fail[now]][i];
else
{
}
fail[next[now][i]]=next[fail[now]][i];
Q.push(next[now][i]);
}
int query(char buf[])
{
int len = strlen(buf);
int now = root;
int res = 0;
for(int i = 0;i < len;i++)
{
8 / 173
ACM 模板
kuangbin