【AtCoder】ABC 430 E - Shift String

2025-11-4

AtCoder/ABC/E問題 AtCoder/ABC/450点問題 AtCoder/緑Diff AtCoder/NoviSteps/1Q AtCoder/文字列探索/KMP法競技プログラミング

E - Shift String

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1109 / NoviSteps: 1Q / 配点: 450 点

問題概要

0, 1からなる長さの等しい文字列 $A,B$ が与えられる。

$A$ に対して以下の操作を $0$ 回以上行うことができる。

$A$ の先頭の文字を末尾に移動させる。

$A=B$ とするために必要な最小の操作回数を求めてよ。ただし、どのように操作しても $A=B$ とできない場合、代わりに $-1$ と出力せよ。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めること。

制約

$1 \le T \le 10000$
$2 \le |A|=|B| \le 10^6$
ひとつの入力について、 $|A|$ の総和は $10^6$ を超えない

考察

操作は文字列 $A$ の左シフトを行うということだが、これは $A + A$ という文字列から連続部分文字列 $B$ を探す問題に帰着させることができる。

このような、ある文字列から特定の部分文字列を探す問題については様々なアルゴリズムが知られているが、ここでは KMP 法を用いて解いてみる。

KMP 法は、「目標の文字列を左から右へ 1 文字ずつずらしながら、探索対象の文字列に対して部分一致するかを判定していく」という流れを基本として、事前に部分マッチテーブルという配列を生成し、それを元に比較を省略できるところを省略しながら効率化を図るアルゴリズムである。

本当に実装を貼り付けるだけなので、詳しいアルゴリズムについては以下の記事を参照のこと。

文字列検索アルゴリズム② ー KMP法 - Qiita

自分の勉強用備忘録を兼ねて自分なりの言葉で色々な文字列検索アルゴリズムについて紹介していこうと思います。本記事では KMP法（Knuth–Morris–Pratt algorithm）について紹介します。 KMP法は文字列探索アルゴリズムの一種で、文字列と文字...

qiita.com

KMP法についてわかりやすく解説（C言語サンプル付き）

今回は文字列検索アルゴリズムの１つである「クヌース – モリス – プラット法」、略して KMP 法について解説していきたいと思います。正直言って、こ ...

だえうホームページ

全体の計算量は $O(\sum |A|)$ であり、本問の制約下では十分高速に動作する。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.vector<int> create_next_table(const string &pattern)
9.{
10.    int n = pattern.size();
11.    vector<int> next(n, 0);
12. 
13.    int j = 0;
14.    rep(i, 1, n)
15.    {
16.        while (j > 0 && pattern[i] != pattern[j])
17.        {
18.            j = next[j - 1];
19.        }
20. 
21.        if (pattern[i] == pattern[j])
22.        {
23.            j++;
24.        }
25. 
26.        next[i] = j;
27.    }
28.    return next;
29.}
30. 
31.int kmp_search(const string &text, const string &pattern)
32.{
33.    int m = text.size();
34.    int n = pattern.size();
35. 
36.    if (n == 0)
37.        return 0;
38. 
39.    if (m < n)
40.        return -1;
41. 
42.    vector<int> next = create_next_table(pattern);
43. 
44.    int j = 0;
45.    rep(i, 0, m)
46.    {
47.        while (j > 0 && text[i] != pattern[j])
48.        {
49.            j = next[j - 1];
50.        }
51. 
52.        if (text[i] == pattern[j])
53.        {
54.            j++;
55.        }
56. 
57.        if (j == n)
58.        {
59.            return i - n + 1;
60.        }
61.    }
62. 
63.    return -1;
64.}
65. 
66.int solve()
67.{
68.    string A, B;
69.    cin >> A >> B;
70. 
71.    string text = A + A;
72.    int ans = kmp_search(text, B);
73. 
74.    return ans;
75.}
76. 
77.int main()
78.{
79.    int T;
80.    cin >> T;
81. 
82.    while (T--)
83.    {
84.        cout << solve() << endl;
85.    }
86. 
87.    return 0;
88.}