[AOJ] No. 0578 看板 (Signboard)

2019年11月15日2019年11月27日

問題

方針

制約が緩いので愚直に文字列を走査していきます。

古い看板から作ることができる看板の例を考えます。例えば、お店の名前の文字列の長さが \( 3 \) であり、古い看板の文字列の長さが \( 7 \) のとき、文字列の添え字を列挙します。

• 間隔が \( 1 \) のとき

\( (1, 2, 3)\), \( (2, 3, 4) \), \( (3, 4, 5) \), \( (4, 5, 6)\), \( (5, 6, 7) \)

• 間隔が \( 2 \) のとき

\( (1, 3, 5)\), \( (2, 4, 6) \), \( (3, 5, 7)\)

• 間隔が \( 3 \) のとき

\( (1, 4, 7)\)

上記のように走査することで回答が得られます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    string t;
    cin >> t;
    string s[N];
    for (int i = 0; i < N; i++) {
        cin >> s[i];
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= s[i].length() - t.length(); j++) {
            for (int k = 1; k < 100; k++) {
                for (int l = 0; l < t.length(); l++) {
                    int idx = j + k * l;
                    if (idx >= s[i].length()) break;
                    if (s[i][idx] != t[l]) break;
                    if (l == t.length() - 1) {
                        ans++;
                        goto loop;
                    }
                }
            }
        }
        loop:;
    }
    cout << ans << "\n";
    return 0;
}