求一个串中是否有happiness，如果有，交换两个字符，是否还能找到happiness，如果还能，输出NO，否则输出YES，然后输出交换的两个字符的下标，情况不唯一。
水题一道，当时写时，数组开小了一倍，runtime error on test 14 好多次，一脸蒙逼。。。
代码写的很冗长，思路很简单。
分情况讨论，
ans==0时，找交换的两个位
ans==1时，直接交换pos和pos+1就行了
ans==2时，交换pos1和pos2+1就行了
ans>2时，NO；
// // main.cpp // 160929 // // Created by 刘哲 on 17/4/30. // Copyright © 2016年 my_code. All rights reserved. // 卧槽，这代码写死我了 //#include <bits/stdc++.h> #include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <string.h> #include <map> #include <set> #include <queue> #include <deque> #include <list> #include <bitset> #include <stack> #include <stdlib.h> #define lowbit(x) (x&-x) typedef long long ll; using namespace std; char a[200000+10],b[10]="happiness"; int p[200000+10],n,m,ans; void fail() { int i,j=-1; p[0]=-1; for(i=1;i<m;i++) { while(j>=0&&b[j+1]!=b[i]) j=p[j]; if(b[i]==b[j+1]) j++; p[i]=j; } } int kmp() { int i,j=-1; ans=0; for(i=0;i<n;i++) { while(j>=0&&b[j+1]!=a[i]) j=p[j]; if(a[i]==b[j+1]) j++; if(j==m-1) { ans++; j=-1; } } return ans; } int main() { scanf("%s",a); string s = a; n=strlen(a); m=9; fail(); int ans = kmp(); // printf("%d\n",kmp()); if(ans>2) cout<<"NO"<<endl; else { cout<<"YES"<<endl; if(ans==0) { for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { swap(a[i],a[j]); if(!kmp()) { cout<<i+1<<' '<<j+1<<endl; return 0; } swap(a[i],a[j]); } } else if(ans==1) { int pos = s.find(b); for(int i=pos;i<pos+9;i++) for(int j=pos;j<pos+9;j++) { swap(a[i],a[j]); if(!kmp()) { cout<<i+1<<' '<<j+1<<endl; return 0; } swap(a[i],a[j]); continue; } } else //2 { int pos1 = s.find(b); int pos2 = s.rfind(b); for(int i=pos1;i<pos1+9;i++) for(int j=pos2;j<pos2+9;j++) { swap(a[i],a[j]); if(!kmp()) { cout<<i+1<<' '<<j+1<<endl; return 0; } swap(a[i],a[j]); continue; } } } return 0; }
// // main.cpp // 160929 // // Created by 刘哲 on 17/4/30. // Copyright © 2016年 my_code. All rights reserved. // 卧槽，这代码写死我了 //#include <bits/stdc++.h> #include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <string.h> #include <map> #include <set> #include <queue> #include <deque> #include <list> #include <bitset> #include <stack> #include <stdlib.h> #define lowbit(x) (x&-x) typedef long long ll; using namespace std; char a[200000+10],b[10]="happiness"; int p[200000+10],n,m,ans; void fail() { int i,j=-1; p[0]=-1; for(i=1;i<m;i++) { while(j>=0&&b[j+1]!=b[i]) j=p[j]; if(b[i]==b[j+1]) j++; p[i]=j; } } int kmp() { int i,j=-1; ans=0; for(i=0;i<n;i++) { while(j>=0&&b[j+1]!=a[i]) j=p[j]; if(a[i]==b[j+1]) j++; if(j==m-1) { ans++; j=-1; } } return ans; } int main() { scanf("%s",a); string s = a; n=strlen(a); m=9; fail(); int ans = kmp(); // printf("%d\n",kmp()); if(ans>2) cout<<"NO"<<endl; else { //cout<<"YES"<<endl; if(ans==0) { for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { swap(a[i],a[j]); if(!kmp()) { cout<<"YES"<<endl<<i+1<<' '<<j+1<<endl; return 0; } if(i==j==n-1) { cout<<"NO"<<endl; return 0; } swap(a[i],a[j]); } } else if(ans==1) { int pos = s.find(b); for(int i=0;i<n;i++) for(int j=pos;j<pos+9;j++) { swap(a[i],a[j]); if(!kmp()) { cout<<"YES"<<endl<<i+1<<' '<<j+1<<endl; return 0; } if(i==n-1&&j==pos+8) { cout<<"NO"<<endl; return 0; } swap(a[i],a[j]); continue; } } else //2 { int pos1 = s.find(b); int pos2 = s.rfind(b); for(int i=pos1;i<pos1+9;i++) for(int j=pos2;j<pos2+9;j++) { swap(a[i],a[j]); if(!kmp()) { cout<<"YES"<<endl<<i+1<<' '<<j+1<<endl; return 0; } if(i==pos1+8&&j==pos2+8) { cout<<"NO"<<endl; return 0; } swap(a[i],a[j]); continue; } } } return 0; }
