KMP算法
在一个字符串S（原串）内查找一个模式串P（字串）的出现位置。 关于next[] 例： 模式串 P=“ababababca” 的部分匹配函数与next函数
可直接使用
void GetNext(char* p
, int next
[])
{
int pLen
= strlen(p
);
next
[0] = -1;
int k
= -1;
int j
= 0;
while (j
< pLen
- 1)
{
if (k
== -1 || p
[j
] == p
[k
])
{
++k
;
++j
;
next
[j
] = k
;
}
else
{
k
= next
[k
];
}
}
}
int KmpSearch(char* s
, char* p
)
{
int i
= 0;
int j
= 0;
int sLen
= strlen(s
);
int pLen
= strlen(p
);
int next
[255];
GetNext(p
, next
);
while (i
< sLen
&& j
< pLen
)
{
if (j
== -1 || s
[i
] == p
[j
])
{
i
++;
j
++;
}
else
{
j
= next
[j
];
}
}
if (j
== pLen
)
return i
- j
;
else
return -1;
}
void kmp_pre(char x
[],int m
,int next
[])
{
int i
,j
;
j
=next
[0]=-1;
i
=0;
while(i
<m
)
{
while(-1!=j
&& x
[i
]!=x
[j
])
j
=next
[j
];
next
[++i
]=++j
;
}
}
void preKMP(char x
[],int m
,int kmpNext
[])
{
int i
,j
;
j
=kmpNext
[0]=-1;
i
=0;
while(i
<m
)
{
while(-1!=j
&& x
[i
]!=x
[j
])j
=kmpNext
[j
];
if(x
[++i
]==x
[++j
])kmpNext
[i
]=kmpNext
[j
];
else kmpNext
[i
]=j
;
}
}
int next
[10010];
int KMP_Count(char x
[],int m
,char y
[],int n
)
{
int i
,j
;
int ans
=0;
kmp_pre(x
,m
,next
);
i
=j
=0;
while(i
<n
)
{
while(-1!=j
&& y
[i
]!=x
[j
])
j
=next
[j
];
i
++;j
++;
if(j
>=m
)
{
ans
++;
j
=next
[j
];
}
}
return ans
;
}
简单例题
Period
#include <cstdio>
#include <iostream>
using namespace std
;
int Next
[1000010];
int n
;
char p
[1000010];
void setNext()
{
int k
=-1;
int j
=0;
Next
[0]=-1;
while(j
<n
)
{
if(k
==-1||p
[j
]==p
[k
])
{
k
++;j
++;
Next
[j
]=k
;
}else{
k
=Next
[k
];
}
}
}
int main()
{
int t
=0;
while(cin
>>n
,n
)
{
cin
>>p
;
setNext();
printf("Test case #%d\n",++t
);
for(int i
=1;i
<=n
;i
++)
{
int len
=i
-Next
[i
];
if(i
!=len
&& i
%len
==0)
printf("%d %d\n",i
,i
/len
);
}
cout
<<endl
;
}
}
