求next数组值

串'ababaaababaa'的next

为：-1 0 0 1 2 3 1 1 2 3 4 5

next

可由next

得，具体

法如下：

 string s = "ababaaababaa"; vector<int> next(s.size()), next val (s.size()); next[0] = -1; int j = -1; for (int i = 1; i < s.size(); i++) { while (j != -1 && s[i] != s[j + 1]) { j = next[j]; } if (s[i] == s[j + 1]) { j++; } next[i] = j; } for (int i = 0; i < s.size(); i++) { if (next[i] == -1 || s[i] != s[next[i]]) { next val [i] = next[i]; } else { next val [i] = next val [next[i]]; } } 

其中，next

的

采用了

算法的思想，next

的

则是在next

的基础上进行的。

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/5025.html