可爱即正义 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; }