作用:用于字符串匹配。
前缀:指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀:指不包含第一个字符的所有以最后一个字符结尾的连续子串。
next[](前缀表):最长前后缀数组。
j是从1开始的;
//如果相等长度+1 if(needle[i] == needle[j]){ j++; next[i] = j; }else{ //回退 j = next[j - 1]; }
完整代码
vector<int> get_next(string& t){ vector<int> next(t.size(), -1); /* j的初始值为-1,值整体右移一位, 这样j对应的位置就是他应该回退的坐标,否则他的前一位才是应该回退的值 */ int i= 0, j = -1; while(i < t.size() - 1){ if(j == -1 || t[i] == t[j]){ j++; i++; next[i] = j; }else{ j = next[j]; } } return next; }
int strStr(string s, string t) { if (t.length() == 0) { return 0; } int n = s.length(); int m = t.length(); vector<int> next = get_next(t); int i = 0, j = 0; while( i < n && j < m){ if(j == -1 || s[i] == t[j]){ j++; i++; if (j == m ) return i - m ; }else{ j = next[j]; } } //未找到返回-1 return -1; }
我们发现2 3 4 5都是多余的判断,因此next[]得到了改良 nextval[]。
vector<int> get_nextval(string& t){ vector<int> nextval(needle.size(), -1); int i= 0, j = -1; while(i < t.size() - 1){ if(j == -1 || t[i] == t[j]){ j++; i++; //如果与s[next[i]]相等则取之前的值 if(t[i] == t[j]){ nextval[i] = nextval[j]; }else{ //如果不等,取现在的值 nextval[i] = j; } }else{ j = nextval[j]; } } return nextval; }
匹配代码不需要改动,只需要next[]替换为nextval[]即可。