Kmpアルゴリズムの完全なコード

10354 ワード

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void GetNext(char s2[], int next[]) {
  int len = strlen(s2);
  int i = 0, j = -1;
  next[0] = -1;
  while (i < len) {
    if (j == -1 || s2[i] == s2[j]) {
      i++; j++;
      next[i] = j;
    }
    else {
      j = next[j];
    }
  }
}
int kmp(char s1[], char s2[], int next[]) {
  int lens1 = strlen(s1);
  int lens2 = strlen(s2);
  int i = 0, j = 0;
  while (i < lens1 && j < lens2) {
    if (j == -1 || s1[i] == s2[j]) {
      i++; j++;
    }
    else {
      j = next[j];
    }
  }
  if (j == lens2) {
    return i-j+1;
  }
  else {
    return -1;
  }
}
int main(){
  int next[15] = {0};
  char s1[100], s2[100];
  cin >> s1 >> s2;
  GetNext(s2, next);
  cout << kmp(s1, s2, next);
  return 0;
}