KMP(三位发明者名字首字母)
next数组表示t[j]以前最长相同前缀后缀
若下标从0开始(以下模板就采用这种方式)，next[ i ] 表示前面下标0~i-1的字符串前缀和后缀相等的最大长度为 next[ i ] 。
若下标从1开始，则next[ i ] 表示前面下标1~i - 1的字符串中前缀和后缀相等的最大长度为 next[ i ] - 1
两种方式当s[i]与t[j]不同时j都应该移动到next[j]
#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 1e6+10;
const int mod = 1e9+7;
const double eps = 1e-9;
char s[maxn], t[maxn];
int nxt[maxn], sl, tl;
void get() {
tl=strlen(t);
nxt[0]=-1; //nxt[0]=-1,nxt[1]=0始终成立
int i=1, j=0; //nxt[0]和nxt[1]都已经定了，因此不需要求了
while(i<tl) { //nxt[tl]用于做循环节相关题目
if(j==-1||t[i]==t[j]) ++i, ++j, nxt[i]=j;
else j=nxt[j];
}
}
int kmp() {
sl=strlen(s);
int i=0, j=0;
while(i<sl&&j<tl) {
if(j==-1||s[i]==t[j]) ++i, ++j;
else j=nxt[j];
}
if(j==tl) return i-j; //求第一个匹配位置，要求所有的话就不要退出
return -1;
}
int main() {
//ios::sync_with_stdio(false);
scanf("%s%s", s, t);
get();
printf("%d\n", kmp());
}
补充：
//nxt[i]=j;
if(s[i]!=t[j]) nxt[i]=j;
else nxt[i]=nxt[j];
//nxt[i]=j的优化版写法
例子(下标从0开始)：
对于T串ababaaababaa的next数组
优化版：-1 0 -1 0 -1 3 1 0 -1 0 -1 3
本质版：-1 0 0 1 2 3 1 1 2 3 4 5
对于T串aabaabaabaab的next数组
优化版：-1 -1 1 -1 -1 1 -1 -1 1 -1 -1 1
本质版：-1 0 1 0 1 2 3 4 5 6 7 8
补充：刘CY老师模板
注意：A, B串均是从下标1开始
void pre() {
P[1]=0;
int j=0;
for(int i=1; j<m; ++i) {
while(j>0 && B[j+1]!=B[i+1]) j=P[j];
if(B[j+1]==B[i+1]) j++;
P[i+1]=j;
}
}
void kmp() {
int ans=0, j=0;
for(int i=0; i<n; ++i) {
while(j>0 && B[j+1]!=A[i+1]) j=P[j]; //不能继续匹配且j还没减少到0，减少j的值
if(B[j+1]==A[i+1]) j++; //能继续匹配，j加1
if(j==m) { //找到一处匹配
printf("%d\n", i-m);//输出子串串首在母串中的位置
j=P[j]; //继续寻找匹配（可重叠）
}
}
}
KMP求最小循环节
cycle=len-next[len];（就这么简单粗暴！next[len]意思是在get()时要处理到字符串末位的后面一位）
cycle指求出的循环节长度，若len%cycle==0，表明字符串是循环的，反之不循环，但可以通过在字符串后面补(cycle-len%cycle)个字符使得字符串变为循环的。
最小循环节例题
Cyclic Nacklace
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18615 Accepted Submission(s): 7601
Problem Description
CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, without any surprise, there are only 99.9 yuan left. he is too distressed and thinking about how to tide over the last days. Being inspired by the entrepreneurial spirit of “HDU CakeMan”, he wants to sell some little things to make money. Of course, this is not an easy task.
As Christmas is around the corner, Boys are busy in choosing christmas presents to send to their girlfriends. It is believed that chain bracelet is a good choice. However, Things are not always so simple, as is known to everyone, girl’s fond of the colorful decoration to make bracelet appears vivid and lively, meanwhile they want to display their mature side as college students. after CC understands the girls demands, he intends to sell the chain bracelet called CharmBracelet. The CharmBracelet is made up with colorful pearls to show girls’ lively, and the most important thing is that it must be connected by a cyclic chain which means the color of pearls are cyclic connected from the left to right. And the cyclic count must be more than one. If you connect the leftmost pearl and the rightmost pearl of such chain, you can make a CharmBracelet. Just like the pictrue below, this CharmBracelet’s cycle is 9 and its cyclic count is 2:
Now CC has brought in some ordinary bracelet chains, he wants to buy minimum number of pearls to make CharmBracelets so that he can save more money. but when remaking the bracelet, he can only add color pearls to the left end and right end of the chain, that is to say, adding to the middle is forbidden.
CC is satisfied with his ideas and ask you for help.
Input
The first line of the input is a single integer T ( 0 < T <= 100 ) which means the number of test cases.
Each test case contains only one line describe the original ordinary chain to be remade. Each character in the string stands for one pearl and there are 26 kinds of pearls being described by ‘a’ ~‘z’ characters. The length of the string Len: ( 3 <= Len <= 100000 ).
Output
For each case, you are required to output the minimum count of pearls added to make a CharmBracelet.
Sample Input
3
aaa
abca
abcde
Sample Output
0
2
5
AC代码
#include "bits/stdc++.h"
using namespace std;
char m[100010];
int nt[100010];
int len;
void Next() {
len=strlen(m);
nt[0]=-1;
int j=0, k=-1;
while(j<len) {
if(k==-1 || m[j]==m[k]) {
j++, k++;
nt[j]=k;
}
else k=nt[k];
}
}
int main() {
int T;
cin>>T;
while(T--) {
scanf("%s", m);
Next();
int cycle=len-nt[len]; //就这么简单
if(cycle<len&&len%cycle==0) printf("0\n");
else printf("%d\n", cycle-len%cycle); //差几个补几个
}
}
EXKMP(扩展KMP，又称Z Algorithm算法)
给出模板串S和串T，长度分别为Slen和Tlen，在线性时间内，对于每个S[i] (0<=i<Slen)，求出S[i…Slen-1]与T的最长公共前缀长度，记为extend[i] (或者说，extend[i]为满⾜足S[i…i+z-1]==T[0…z-1]的最⼤的z值)。
#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;
char s[maxn], p[maxn];
int f[maxn], extend[maxn], sl, pl; // f为p串的extend数组，extend为p串在s串上的extend数组
void getf() { //得到f数组
f[0]=pl=strlen(p);
int a=0;
while(a<pl-1&&p[a]==p[a+1]) a++;
f[1]=a, a=1;
for(int k=2; k<pl; ++k) {
int l=f[k-a], r=a+f[a]-1;
if(k-1+l>=r) {
int j=(r-k+1)>0?(r-k+1):0;
while(k+j<pl&&p[k+j]==p[j]) j++;
f[k]=j, a=k;
}
else f[k]=l;
}
}
void get() { //得到extend数组
sl=strlen(s), pl=strlen(p);
int a=0, mlen=sl<pl?sl:pl;
while(a<mlen&&s[a]==p[a]) a++;
extend[0]=a, a=0;
for(int k=1; k<sl; k++) {
int l=f[k-a], r=a+extend[a]-1;
if(k-1+l>=r) {
int j=(r-k+1)>0?(r-k+1):0;
while(k+j<sl&&j<pl&&s[k+j]==p[j]) j++;
extend[k]=j, a=k;
}
else extend[k]=l;
}
}
int main() {
//ios::sync_with_stdio(false);
scanf("%s%s", p, s);
getf();
get();
}
扩展KMP例题
Best Reward
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4769 Accepted Submission(s): 1958
Problem Description
After an uphill battle, General Li won a great victory. Now the head of state decide to reward him with honor and treasures for his great exploit.
One of these treasures is a necklace made up of 26 different kinds of gemstones, and the length of the necklace is n. (That is to say: n gemstones are stringed together to constitute this necklace, and each of these gemstones belongs to only one of the 26 kinds.)
In accordance with the classical view, a necklace is valuable if and only if it is a palindrome - the necklace looks the same in either direction. However, the necklace we mentioned above may not a palindrome at the beginning. So the head of state decide to cut the necklace into two part, and then give both of them to General Li.
All gemstones of the same kind has the same value (may be positive or negative because of their quality - some kinds are beautiful while some others may looks just like normal stones). A necklace that is palindrom has value equal to the sum of its gemstones’ value. while a necklace that is not palindrom has value zero.
Now the problem is: how to cut the given necklace so that the sum of the two necklaces’s value is greatest. Output this value.
Input
The first line of input is a single integer T (1 ≤ T ≤ 10) - the number of test cases. The description of these test cases follows.
For each test case, the first line is 26 integers: v1, v2, …, v26 (-100 ≤ vi ≤ 100, 1 ≤ i ≤ 26), represent the value of gemstones of each kind.
The second line of each test case is a string made up of charactor ‘a’ to ‘z’. representing the necklace. Different charactor representing different kinds of gemstones, and the value of ‘a’ is v1, the value of ‘b’ is v2, …, and so on. The length of the string is no more than 500000.
Output
Output a single Integer: the maximum value General Li can get from the necklace.
Sample Input
2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
aba
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
acacac
Sample Output
1
6
AC题解
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
using namespace std;
char str1[500005],str2[500005];
int nt[500005],extend1[500005],extend2[500005];
int v[26],sum[500005];
//扩展KMP是用来求主串每个点可以向后延伸与模式串匹配的最长的长度
void EKMP(char t[],char s[],int nt[],int extend[])
{ //t为模式串,s为主串
int i,j,p,a,b;
int lent=strlen(t);
int lens=strlen(s);
nt[0]=lent; j=0;
while(j+1<lent&&t[j]==t[j+1])
j++;
nt[1]=j; //先是模式串自匹配
a=1;
for(i=2;i<lent;i++)
{
p=nt[a]+a-1;
b=nt[i-a];
if(i+b<p+1)
nt[i]=b;
else
{
j=max(0,p-i+1);
while(i+j<lent&&t[i+j]==t[j])
j++;
nt[i]=j;
a=i;
}
}
j=0;
while(j<lens&&j<lent&&s[j]==t[j])
j++;
extend[0]=j;
a=0;
for(i=1;i<lens;i++)
{
p=extend[a]+a-1;
b=nt[i-a];
if(i+b<p+1)
extend[i]=b;
else
{
j=max(0,p-i+1);
while(i+j<lens&&j<lent&&s[i+j]==t[j])
j++;
extend[i]=j;
a=i;
}
}
}
int main()
{
int tes,i;
scanf("%d",&tes);
while(tes--)
{
for(i=0;i<26;i++) scanf("%d",&v[i]);
scanf("%s",str1);
int len=strlen(str1);
sum[0]=0;
for(i=0;i<len;i++)
{
str2[i]=str1[len-1-i];
sum[i+1]=sum[i]+v[str2[i]-'a'];
}
str2[len]='\0';
EKMP(str1,str2,nt,extend1); //str1是模式串
EKMP(str2,str1,nt,extend2); //str2是模式串
int res=-1000000;
for(i=1;i<len;i++) //0~i-1与i~len-1
{
int tmp=0;
//对串2来说,前len-i回文
if(i+extend2[i]>=len) tmp+=sum[len-i];
int pos=len-i;
//对串2来说,后i个回文
if(pos+extend1[pos]>=len)
tmp+=sum[len]-sum[pos];
if(tmp>res)
res=tmp;
}
printf("%d\n",res);
}
return 0;
}
京公网安备 11010502036488号