今天leetcode做了个动态规划的题。字符串匹配。今天处理的都是和字符串相关。
嗷今天另一大收获是看了看谷歌的cpp编码规范。它的有个好处是条款原因写的很清楚。以后有感想再说吧。
先把Effective cpp看起来。
话不多说，kmp启动。

KMP

KMP主要是利用过已经匹配过的信息继续匹配。
比如ABABABABC与ABABC匹配。到 [4] 时发现字符不匹配，不需要重新开始匹配。我们知道前4个字符已经匹配了。所以可以研究一下前4个字符的性质。如果前n个字符的[n-k，n）字符与前[0，k）个字符相等，可以直接移动到 k处。
有关模式字符串的信息是可以提前计算的，这个数组叫next。
next数组可以动态规划。用x表示后缀的最后一个位置。now表示前缀的最后一个位置。x == now，皆大欢喜，next++。如果不等于，now = next[x-1]。这里很妙。明天细讲吧。困了。
贴上我学习的连接🔗
https://www.zhihu.com/question/21923021/answer/1032665486?utm_source=qq&utm_medium=social&utm_oi=74678236348416&utm_content=sec

最终代码如下

#include <cstdio>
#include <cstring>

using namespace std;

char s[1000010], t[1000010];
int next[1000010];

int main(void) {
 scanf("%s", s);
 scanf("%s", t);
 int m = strlen(s), n = strlen(t);
 int x = 1, now = 0;
 while (x < n) {
   if (t[now] == t[x]) {
     next[x] = ++now;
     ++x;
   } else if (now != 0) {
     now = next[now - 1];
   } else {
     x++;
   }
 }
 int tar = 0, pos = 0;
 while (tar < m) {
   if (s[tar] == t[pos]) {
     ++tar;
     ++pos;
   } else if (pos != 0) {
     pos = next[pos - 1];
   } else {
     ++tar;
   }
   if (pos == n) {
     printf("%d\n", tar - pos + 1);
     pos = next[pos - 1];
   }
 }
 for (int i = 0; i < n; ++i) {
   printf("%d ", next[i]);
 }
 return 0;
}

今天理了发，玩的有点久了，就先这样吧。明天加一点内容。
:) 说实话我代码写的挺漂亮的。