1.模板题：
给定两个数字序列 a[] 和 b[]，b[] 有可能整体作为一个连续子序列出现在了 a[] 中，现在请你找出 b[] 在 a[] 中第一次出现的位置（起始位置从 1 开始计数），如果一次都没有出现，请输出 -1。
输入格式
第一行包含一个数字 T，表示测试用例的个数。
对于每组测试用例，第一行包含两个数字 n m ( 1<= n <= 1000000, 1 <= m <= 10000 )，表示 a[] 和 b[] 的长度。
接下来的一行包括 n 个数字，依次表示 a[1], a[2], a[3] ... a[n]，-1000000 <= a[i] <= 1000000
接下来的一行包括 m 个数字，依次表示 b[1], b[2], b[3] ... b[m]，-1000000 <= b[i] <= 1000000
输出格式
对于每组数据输出一行，请输出 b[] 整体作为一个连续子序列在 a[] 中的首次出现位置的起始下标，如果一次都没有完整出现，输出 -1。
样例输入
2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1
样例输出
6
-1
样例解释
对于第一组数据，1 2 1 2 3 [1 2 3 1 3] 2 1 2，首次出现位置的起始下标为 6。
对于第二组数据，b[] 没有出现在 a[] 中，输出 -1。
#pragma GCC optimize(2)
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
typedef long long ll;
ll read(){
ll x=0; ll f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
using namespace std;
const int maxn=5e6+100;
int s[maxn];
int p[maxn];
int ne[maxn];
int n,m;
void getnext(){
int j=0,k=-1;
ne[0]=-1;
while(j<m){
if(k==-1||p[j]==p[k]){
j++;
k++;
ne[j]=k;
}
else{
k=ne[k];
}
}
}
int kmp(){
int i=0,j=0;
getnext();
while(i<n){
if(j==-1|s[i]==p[j]){
i++;
j++;
}
else{
j=ne[j];
}
if(j==m){
return i;
}
}
return -1;
}
int main(){
int t;
cin>>t;
while(t--){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>s[i];
}
for(int i=0;i<m;i++){
cin>>p[i];
}
if(kmp()==-1){
cout<<-1<<endl;
}
else{
cout<<kmp()-m+1<<endl;
}
}
}
2.传送门
求模式串在待匹配串中的出现次数。
Input
第一行是一个数字T，表明测试数据组数。之后每组数据都有两行： 第一行为模式串，长度不大于10,000； 第二行为待匹配串，长度不大于1,000,000。（所有字符串只由大写字母组成）
Output
每组数据输出一行结果。
Sample Input
4 ABCD ABCD SOS SOSOSOS CDCDCDC CDC KMP SOEASY
Sample Output
1 3 0 0
这个题是出现次数例如：
这个是出现了几次例如
aa
aaaa
这个是三次
下一个题和这一个不一样
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
/*
这个是出现了几次例如
aa
aaaa
这个是三次
*/
const int maxn=1e6+100;
char a[maxn];
char b[maxn];
int ne[maxn];
int lena,lenb;
void getnext(){
int j=0,k=-1;
ne[0]=-1;
while(j<lena){
if(k==-1||a[j]==a[k]){
j++;
k++;
ne[j]=k;
}
else{
k=ne[k];
}
}
}
int kmp(){
int i=0,j=0;
int ans=0;
getnext();
while(j<lenb){
if(i==-1||a[i]==b[j]){
i++;
j++;
}
else{
i=ne[i];
}
if(i==lena){
//i=ne[i];
ans++;
}
}
return ans;
}
int main(){
int t;
cin>>t;
while(t--){
scanf("%s%s",a,b);
lena=strlen(a);
lenb=strlen(b);
cout<<kmp()<<endl;
}
}
一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？
Input输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。
Output输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。
Sample Input
abcde a3 aaaaaa aa #
Sample Output
0 3
这个题和上一个不一样：
这个就是不能重复
例如：
aa
aaaa 为2
aa
aaaaaa 为3
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
/*
这个就是不能重复
例如：
aa
aaaa 为2
aa
aaaaaa 为3
*/
char a[maxn];//长串
char b[maxn];//短串
int ne[maxn];
int lena,lenb;
void getnext(){
int j=0,k=-1;
ne[0]=-1;
while(j<lena){
if(k==-1||a[j]==a[k]){
j++;
k++;
ne[j]=k;
}
else{
k=ne[k];
}
}
}
int kmp(){
int i=0,j=0;
int ans=0;
getnext();
while(j<lenb){
if(i==-1||a[i]==b[j]){
i++;
j++;
if(i==lena){
ans++;
i=0;
}
}
else{
i=ne[i];
}
}
return ans;
}
int main(){
while(~scanf("%s",b)){
if(b[0]=='#'){
break;
}
scanf("%s",a);
lena=strlen(a);
lenb=strlen(b);
cout<<kmp()<<endl;
}
}
next数组的应用
1.传送门
WenDavid喜欢周期循环，看到不是周期循环的字符串就很不爽。 现在WenDavid得到一个字符串，可以在字符串末尾添加若干字符，请你帮WenDavid想想，最少添加多少个字符，才能使得字符串变得周期循环（即至少出现两个循环节）。
Input
第一行是一个整数 T ( 0<T<=100 ) 代表测试数据的组数。 之后T行每行一个字符串，由小写字母组成，字符串的长度3<=L<=100000。
Output
每组数据输出一行结果。
Sample Input
3 ppp pip machinelearning
Sample Output
0 1 15
循环节长度
int m=len-Next[len];
if(len%m==0)//这个是代表是不是真好够整个循环 cout<<m <<endl; //每个循环节的长度 cout<<len/m<<endl; //循环几次
解析：
m=lena-ne[lena]，这个是循环节，
lena%m==0&&lena/m>=2这个是说正好是一个循环，并且循环长度大于2
m-lena%m//是补充几个构成循环
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
char a[maxn];
int ne[maxn];
int lena,lenb;
void getnext(){
int j=0,k=-1;
ne[0]=-1;
while(j<lena){
if(k==-1||a[j]==a[k]){
j++;
k++;
ne[j]=k;
}
else{
k=ne[k];
}
}
}
int main(){
int t;
cin>>t;
while(t--){
scanf("%s",a);
lena=strlen(a);
getnext();
int ans=0;
int m=lena-ne[lena];//循环节
if(lena%m==0&&lena/m>=2){//至少右一个循环节
cout<<0<<endl;
}
else{
cout<<m-lena%m<<endl;
}
}
}
判断循环节和一个循环
cgg给你一个字符串s,问在所有的[0, i]区间是否有完整的循环节,若有,输出i并输出循环次数。（嗯哼，就是这么简单的题意）
Input
输入包含多组样例。
每组数据两行，第一行一个整数n（2<=n<=1000000）,为字符串的长度，第二行包含一个字符串。
数据以单个0结尾
Output
对于每个测试用例，在一行上输出“ Test case＃”和连续的测试用例编号；
然后，对于长度为i且循环次数K> 1的每个前缀，输出前缀大小i和以单个空格分隔的循环次数K； 前缀大小必须按升序排列。 在每个测试用例之后打印空白行。
Sample Input
3 aaa 12 aabaabaabaab 0
Sample Output
Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4
判断是不是一整个循环
int p=i-ne[i];
if(i%p==0&&ne[i]!=0){
cout<<i<<" "<<i/p<<endl;
}
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
char a[maxn];
int ne[maxn];
int lena;
void getnext(){
int j=0,k=-1;
ne[0]=-1;
while(j<lena){
if(k==-1||a[j]==a[k]){
j++;
k++;
ne[j]=k;
}
else{
k=ne[k];
}
}
}
int main(){
int kase=1;
while(cin>>lena&&lena){
scanf("%s",a);
getnext();
printf("Test case #%d\n",kase++);
for(int i=1;i<=lena;i++){
int p=i-ne[i];
if(i%p==0&&ne[i]!=0){
cout<<i<<" "<<i/p<<endl;
}
}
cout<<endl;
}
}
输出循环次数：
给定若干个长度 ≤ 1000000 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有 3 个 ab 连接而成。
输入格式
输入若干行，每行有一个字符串，字符串仅含英语字母。
输入数据以"."结束。
输出格式
对于每组输入数据输出一行，找出每个字符串最多是由多少个相同的子字符串重复连接而成的。
样例输入
abcd
aaaa
ababab
.样例输出
1
4
3#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
char a[maxn];
int ne[maxn];
int lena;
void getnext(){
int j=0,k=-1;
ne[0]=-1;
while(j<lena){
if(k==-1||a[j]==a[k]){
j++;
k++;
ne[j]=k;
}
else{
k=ne[k];
}
}
}
int main(){
while(scanf("%s",a)){
if(a[0]=='.'){
break;
}
lena=strlen(a);
getnext();
int ans=1;
int p=lena-ne[lena];
if(lena%(lena-ne[lena])==0){
ans=lena/(lena-ne[lena]);
}
cout<<ans<<endl;
}
}
题意：一个字符串，求符合EAEBE形式情况下最大E子串的长度
思路：前缀E和后缀E可以用next数组求出，然后在判断中间的E是否存在，具体做法是：next[len]=i，在[2 * i ,len - i](因为不能重合)内找是否有next[j]=i，存在则i就为答案，不存在的话令i=next[i],而不是i--，继续找
这个题不理解的话可以自己画一下
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
char a[maxn];
int ne[maxn];
int lena;
void getnext(){
int j=0,k=-1;
ne[0]=-1;
while(j<lena){
if(k==-1||a[j]==a[k]){
j++;
k++;
ne[j]=k;
}
else{
k=ne[k];
}
}
}
int main(){
int t;
cin>>t;
while(t--){
scanf("%s",a);
lena=strlen(a);
getnext();
int ans=0;
for(int i=ne[lena];i;i=ne[i]){//就是缩小公共前后缀
for(int j=i*2;j<=lena-i;j++){
if(ne[j]==i){/说明和开头一样
ans=i;
break;
}
}
if(ans){
break;
}
}
cout<<ans<<endl;
}
}
就是找一个k和p,让去掉前k个字母剩下的形成的循环节为p,让求k+p最小的情况下k最小
这个题就是把字符串反转然后再求
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn=1e6+100;
int a[maxn];
int b[maxn];
int ne[maxn];
void getnext(int l){
int j=0,k=-1;
ne[0]=-1;
while(j<l){
if(k==-1||a[j]==a[k]){
j++;
k++;
ne[j]=k;
}
else
k=ne[k];
}
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>b[i];
}
for(int i=0,j=n-1;i<n;i++,j--){
a[i]=b[j];
}
getnext(n);
int z=0x3f3f3f3f;
int ans1=0;
int ans2=n-ne[n];
for(int i=1;i<=n;++i){
int k=n-i;
int p=i-ne[i];
if(k+p<z){
z=k+p;
ans1=k;
ans2=p;
}
else if(k+p==z&&ans2>p){
ans1=k;
ans2=p;
}
}
printf("%d %d\n",ans1,ans2);
}
标签：lena,int,ne,while,maxn,kmp,include From： https://www.cnblogs.com/lipu123/p/14599558.html