可爱即正义 KMP匹配

只能交换两个字符的一次，设成功匹配子串的字数为n
n＞2时，No
n=2时，交换第一个子串的第一字母和第二子串的第二字母即可
n=1或n=0时，原理差不多，一个一个尝试交换后每次都进行kmp匹配寻找子串个数，

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+7;
int nt[MAX];
int a=0,b=0;
void kmp_next(string pattern,int next[])
{
    int len=pattern.size();
    next[0]=-1;
    for(int i=0,j=-1;i<len;)
    {
        if(j==-1||pattern[i]==pattern[j])
        {
            next[++i]=++j;
        }
        else
            j=next[j];
    }
}
int kmp(string s,string pattern,int next[])
{
    int ls=s.size(),lp=pattern.size(),flag=0;
    for(int i=0,j=0;i<ls;)
    {
        if(j==-1||s[i]==pattern[j]){
            i++,j++;
        }
        else j=next[j];
        if(j==lp){
            flag++;
            j=0;
            if(flag==1)a=i-lp;
            else if(flag==2)b=i-lp;
        }    
    }
    return flag;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    string s,pattern="suqingnianloveskirito";
    cin>>s; 
    if(s.size()<pattern.size()){
        cout<<"Yes"<<endl;
        cout<<1<<" "<<2;
        return 0;
    }
    else{
        kmp_next(pattern,nt);
        int n=kmp(s,pattern,nt);
        if(n>2){
            cout<<"No";
            return 0;
        }
        else if(n==2){
            cout<<"Yes"<<endl;
            cout<<a+1<<" "<<b+2;
            return 0;
        }
        else if(n==1){
            int f=0;
            for(int i=a;i<a+pattern.size();i++)
            {
                for(int j=0;j<s.size();j++)
                {
                    if(i!=j&&s[i]!=s[j])
                    {
                        swap(s[i],s[j]);
                        if(kmp(s,pattern,nt)==0){
                        cout<<"Yes"<<endl;
                        cout<<i+1<<" "<<j+1;
                              return 0; 
                        }
                        else swap(s[i],s[j]);
                    }
                }
            }
            cout<<"No";
        }
        else {
            int f=0;
            for(int i=0;i<s.size();i++)
            {
                for(int j=i+1;j<s.size();j++)
                {
                    if(s[i]!=s[j])
                    {
                        swap(s[i],s[j]);
                        if(kmp(s,pattern,nt)==0){
                            cout<<"Yes"<<endl;
                            cout<<i+1<<" "<<j+1;
                            return 0; 
                        }
                        else swap(s[i],s[j]);    
                    }
                }
            }
            cout<<"No";
        }
    }
   return 0;
}