牛客18984 可爱即正义 KMP

可爱即正义 KMP二星水题 传送门

题目描述

小可爱是个可爱的女孩子(nzdl)。
众所周知，小可爱在物竞初赛时候有两道大题没有做出来，所以，可爱的小可爱(qwq)便沉浸在了毒瘤之中——无法接受在任何地方看到"suqingnianloveskirito"这个东西。然而，这时候从SD某处送来了一封安慰信(情书)，信的内容是一个26个小写拉丁字母组成的字符串s。这封信提前被wyxdrqc劫了下来(没错，就是这个劫)，他打开了这封信，结果发现了满篇的"suqingnianloveskirito"所以他想篡改这封信。
由于他的能力有限，所以他只能把这个字符串的其中两个位置上的字符互换，而且只能操作一次。
他现在想问你，通过他的操作能不能使"suqingnianloveskirito"不是这个字符串的子串。

输入描述

一行一个字符串s

输出描述

如果他能通过只交换其中的两个位置上的字符使"suqingnianloveskirito"不是交换后的字符串的子串，则在第一行输出一个Yes，之后一行输出两个数d1，d2，表示你的方案是把原字符串在位置d1和位置d2上的字符互换，字符串的第一个字符的位置是1。
如果他不管交换那两个字符都不能满足条件，直接输出一行No。

题解

对字符串pattern=“suqingnianloveskirito”，进行kmp前缀处理获得next数组，然后让输入字符串s进行kmp匹配，返回s中含有n个字符串pattern，并记录第一次和第二次子串的首位置的下标。
因为只能交换字符串s的中的两个字符，故
①n＞2时，NO
②n=2时，YES，可交换第一个子串的第一个字符和第二个子串的第二个字符
③n=1时，在从子串中首位置和字符串s首位置开始一个一个交换后尝试kmp字符串匹配，直到交换出符合条件的位置
④n=0时，若s的长度小于pattern的长度，故肯定存在，随机交换即可；若s的长度大于pattern的长度，就可以尝试s[0]与s[1]，s[0]与s[2]…s[0]与s[s.size()-1]，s[1]与s[2]，s[1]与s[3]交换，直到尝试出kmp字符串匹配返回匹配成功次数为0为止

#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;
}

本文地址：https://blog.csdn.net/hrd535523596/article/details/107131349