kmp

可爱即正义

该模式串无论交换哪两个都不可能匹配自己，分类讨论
//注意下标从1开始strlen(s+1)

#include<bits/stdc++.h>
#include<cstring>
#include<string.h>
using namespace std;
const int N=1e6+10;
int ne[N];
char s[N],p[N]={" suqingnianloveskirito"};
int n,m,ans=0;
int idx1,idx2;
void getnext()
{
    for(int i=2,j=0;i<=m;i++)
    {
        while(j&&p[j+1]!=p[i]) j=ne[j];
        if(p[j+1]==p[i]) j++;
        ne[i]=j;
    }
}
void kmp()
{
    for(int i=1,j=0;i<=n;i++)
    {
        while(j&&p[j+1]!=s[i]) j=ne[j];
        if(p[j+1]==s[i]) j++;
        if(j==m)
        {
            ans++;
            j=ne[j];
            if(ans==1)
                idx1=i-m+1;
            else if(ans==2)
                idx2=i-m+1;
        }
    }
}
int main()
{
    m=strlen(p)-1;
    cin>>s+1;
    n=strlen(s+1);
    getnext();
    kmp();
    if(ans==0)
    {
            printf("YES\n");
            cout<<"1 2"<<endl;
    }
    else if(ans==1)
    {
            printf("YES\n");
            cout<<idx1<<" "<<idx1+1<<endl;
    }
    else if(ans==2)
    {
            printf("YES\n");
            cout<<idx1<<" "<<idx2+1<<endl;
    }
    else if(ans>2)
            printf("NO\n");
    return 0;
}

Youhane Assembler

把提供后缀的串接在提供前缀的串前面，得到新串str，求str的next数组，next[str.length]就是最长相同前后缀的长度，中间连接处添加了一个其他字符，所以l的后缀肯定不会用到r的前缀。

#include<bits/stdc++.h>
using namespace std;
const int MAX=3e6+10;
string s[MAX];
string str;
int ne[MAX];
void getnext(int length,string p)
{
    for(int i=2,j=0;i<=length;i++)
    {
        while(j&&p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i]=j;
    }
}
int main()
{
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i];
    cin>>m;
    for(int i=0;i<m;i++)
    {
        int l,r;
        cin>>l>>r;
        str=s[r]+"#"+s[l];
        str="0"+str;
        getnext(str.size()-1,str);
        cout<<ne[str.size()-1]<<endl;
    }
}

子串

进制处理配对一下就好了
//进制配对的时候i要另外设变量存储，不然就死循环了

#include<bits/stdc++.h>
#include<cstring>
#include<string>
using namespace std;
const int N=1e6+10;
int ne[N];
string s,p;
int len1,len2;
string getstring(int k,int n)//把1~n在k进制下连接起来
{
    string temp="";
    for(int i=1;i<=n;i++)
    {
        string str="";
        int p=i;//卧槽！！！
        while(p>0)
        {
            int num=p%k;
            char t;
            if(num>=10)
                t=num-10+'A';
            else
                t=num+'0';
            str=t+str;
            p/=k;
        }
        temp+=str;
    }
    return temp;
}
void getnext()
{
    for(int i=2,j=0;i<=len2;i++)
    {
        while(j&&p[i]!=p[j+1]) j=ne[j];
        if(p[j]==p[j+1]) j++;
        ne[i]=j;
    }
}
bool kmp()
{
    for(int i=1,j=0;i<=len1;i++)
    {
        while(j&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==len2)
        {
            return true;
        }
    }
    return false;
}
int main()
{
    int n;
    cin>>n>>p;
    p="0"+p;
    len2=p.size()-1;
    for(int i=2;i<=16;i++)
    {
        s=getstring(i,n);
        s="0"+s;
        len1=s.size()-1;
        getnext();
        if(kmp())
        {
            printf("yes\n");
            return 0;
        }
    }
    printf("no\n");
    return 0;
}

E、Sort String

最小循环节的理解，传送门~~~，这题亲测cout和printf得运算时间有差10倍。。

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
const int N=1e6+10;
int ne[N];
char p[N];
int n;
void getnext()
{
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i]=j;
    }
}
int main()
{
    cin>>p+1;
    n=strlen(p+1);
    getnext();
    int k=n-ne[n];//最小循环节
    printf("%d\n",k);
    if(n%k==0)//如果有循环周期
    {
        for(int i=0;i<k;i++)
        {
            printf("%d",n/k);
            for(int j=i;j<n;j+=k)
                printf(" %d",j);
            printf("\n");
        }
    }
    else
    {
        for(int i=0;i<n;i++)
            printf("1 %d\n",i);
    }
}