28. 实现 strStr()
难点:
1,制作KMP算法
2,next 数组要求的是,找到的下标:0/ s[i]==s[j]才可以跳出来
代码:
1 vector<int> getNextList(string needle) 2 { 3 vector<int> next(needle.size()); 4 int j = 0; 5 next[0]=0; 6 7 for (int i = 1; i < needle.size(); i++) 8 { 9 while (j > 0 && needle[j] != needle[i]) 10 { 11 j = next[j - 1]; 12 } 13 14 if (needle[i] == needle[j]) 15 { 16 j++; 17 } 18 19 next[i] = j; 20 } 21 22 return next; 23 } 24 25 26 int strStr(string haystack, string needle) 27 { 28 if (needle.size() == 0) { 29 return 0; 30 } 31 32 auto next = getNextList(needle); 33 34 int i = 0; 35 for (int j = 0; j < haystack.size(); j++) 36 { 37 while (i > 0 && needle[i] != haystack[j]) 38 { 39 40 i = next[i - 1]; 41 cout << i; 42 43 } 44 45 if (haystack[j] == needle[i]) 46 { 47 i++; 48 } 49 50 if (i == needle.size()) 51 return j - needle.size() + 1; 52 } 53 54 return -1; 55 }
标签:459,strStr,int,28,needle,随想录,next,size From: https://www.cnblogs.com/smartisn/p/17484203.html