1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
|
#include <string>
using namespace std;
int (string s,string t) { int i=0,j=0; while(i<s.length()&&j<t.length()) { if(s[i]==t[j]) { i++; j++; } else { i = i - j + 1; j = 0; } } if(j>=t.length()) return i-t.length(); else return -1; } int * getNext(string t,int next[]) { next[0] = -1; int k=-1,i=0; while(i<t.length()-1) { if (k == -1 || t[i] == t[k]) { if (t[i + 1] == t[k + 1]) { next[++i] = next[++k]; } else { next[++i] = ++k; } } else { k = next[k]; } } return next; } int kmp(string s,string t) { if(s=="" || t=="") return -1; int *next = new int[s.length()]; getNext(t,next);
int i=0; int j = -1; int t_len = t.length(); int s_len = s.length(); while( i < s_len && j < t_len) { if(j==-1||s[i]==t[j]) { i++; j++; } else { j = next[j]; } } if(j>=t.length())return i-t.length(); else return -1; } int main() { string s,t; cin>>s>>t; cout<<Index(s,t)<<endl; cout<<kmp(s,t)<<endl; return 0; }
|
近期评论