LOJ #103. 子串查找 && KMP複習

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
int nxt[A], n, k, len1, len2, ans;
char s1[A], s2[A];

int main(int argc, char const *argv[]) {
  cin >> s1 >> s2; len1 = strlen(s1); len2 = strlen(s2);
  int i = 0, j = -1; nxt[0] = -1;
  while (i < len2)
    if (j == -1 or s2[i] == s2[j]) nxt[++i] = ++j;
    else j = nxt[j]; //求自身的next數組
  i = 0; j = 0;
  while (i < len1) {
    if (j == -1 or s1[i] == s2[j]) i++, j++;
    else j = nxt[j];
    if (j == len2) ans++, j = nxt[j];
  }
  cout << ans << endl;
}