test/string/KMP.test.cpp

• View this file on GitHub
• Last update: 2026-07-19 04:18:57+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B

Depends on

• KMP 法 (Knuth–Morris–Pratt algorithm) (src/string/KMP.hpp)
• test/template.hpp

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
#include "test/template.hpp"
#include "src/string/KMP.hpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   string S, T;
   cin >> S >> T;
   auto s = T + '$' + S;
   auto kmp = KMP(s);

   rep(i, sz(s) - sz(S), sz(s)) {
      if(kmp[i] == sz(T)) cout << i - sz(T) * 2 << '\n';
   }
}

#line 1 "test/string/KMP.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
template<class T> using V = vector<T>;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define each(i, a) for(auto&& i : a)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 1 "src/string/KMP.hpp"
// kmp[i] := max{ l ≤ i | s[:l] == s[(i+1)-l:i+1] }
// abacaba -> 0010123
auto KMP(string s) {
   V<ll> p(sz(s));
   rep(i, 1, sz(s)) {
      ll g = p[i - 1];
      while(g && s[i] != s[g]) g = p[g - 1];
      p[i] = g + (s[i] == s[g]);
   }
   return p;
}
#line 4 "test/string/KMP.test.cpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);
   string S, T;
   cin >> S >> T;
   auto s = T + '$' + S;
   auto kmp = KMP(s);

   rep(i, sz(s) - sz(S), sz(s)) {
      if(kmp[i] == sz(T)) cout << i - sz(T) * 2 << '\n';
   }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00	AC	2 ms	4 MB
g++	01_small_00	AC	2 ms	4 MB
g++	01_small_01	AC	2 ms	4 MB
g++	01_small_02	AC	2 ms	4 MB
g++	01_small_03	AC	2 ms	4 MB
g++	02_rand_00	AC	3 ms	4 MB
g++	02_rand_01	AC	2 ms	4 MB
g++	02_rand_02	AC	2 ms	4 MB
g++	02_rand_03	AC	2 ms	4 MB
g++	02_rand_04	AC	2 ms	4 MB
g++	02_rand_05	AC	2 ms	4 MB
g++	02_rand_06	AC	2 ms	4 MB
g++	02_rand_07	AC	3 ms	5 MB
g++	03_large_00	AC	2 ms	4 MB
g++	03_large_01	AC	2 ms	4 MB
g++	03_large_02	AC	3 ms	4 MB
g++	03_large_03	AC	3 ms	4 MB
g++	03_large_04	AC	8 ms	14 MB
g++	03_large_05	AC	9 ms	14 MB
g++	03_large_06	AC	8 ms	14 MB
g++	03_large_07	AC	8 ms	14 MB
g++	03_large_08	AC	9 ms	14 MB
g++	03_large_09	AC	8 ms	14 MB
g++	04_embedded_00	AC	11 ms	14 MB
g++	04_embedded_01	AC	11 ms	14 MB
g++	04_embedded_02	AC	8 ms	14 MB
g++	04_embedded_03	AC	8 ms	14 MB
g++	04_embedded_04	AC	8 ms	14 MB
g++	04_embedded_05	AC	8 ms	14 MB
g++	05_corner_00	AC	2 ms	4 MB
g++	05_corner_01	AC	2 ms	4 MB
g++	05_corner_02	AC	2 ms	4 MB
g++	05_corner_03	AC	52 ms	14 MB
g++	05_corner_04	AC	49 ms	14 MB
g++	05_corner_05	AC	9 ms	14 MB
g++	05_corner_06	AC	7 ms	14 MB

Back to top page