Quiz

No.1005 BOT対策 https://yukicoder.me/problems/no/1005

AC code

説明

別解でO(N)で解ける方法としてZアルゴリズムが挙げられている
- 先頭とどれだけ一致するかが分かる
使ったことが1度だけあるが、再度使って練習してみた
文字列sから文字列tを探すとして、t+sをZアルゴリズムの入力とする
具体例としてサンプルを使うと

// 入力
s = doyouknowsegmenttreeiknowsegmenttree
t = segmenttree

// 出力
2

// 補足
文字列の長さ|t| = 11
Zアルゴリズムの出力で11以上のところにtが存在する

sの長さは36
tの長さは11
Zアルゴリズムの出力は

{
47, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 
11, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 
0, 11, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 
0
}

f:id:peroon:20200311023251p:plain

tの長さである11以上の数字が現れた箇所にtが存在する
あとは解説通り、s内で見つけたtの右端にピリオドを打てばいい

code 抜粋

VI Z_algorithm(const string &S) {
    int N = (int)S.size();
    VI res(N);
    res[0] = N;
    int i = 1, j = 0;
    while (i < N) {
        while (i+j < N && S[j] == S[i+j]) ++j;
        res[i] = j;
        if (j == 0) {++i; continue;}
        int k = 1;
        while (i+k < N && k+res[k] < j) res[i+k] = res[k], ++k;
        i += k, j -= k;
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    string s,t;cin>>s>>t;
    debug(s, s.size());
    debug(t, t.size());
    ll L = s.size();
    ll M = t.size();
    string u = t+s;
    VI A = Z_algorithm(u);
    debug(A);

    // 無理な場合があるとすればこれのみ
    if(M==1){
      bool exist = false;
      for(char c : s){
        if(c==t[0]) exist=true;
      }
      if(exist){
        p(-1);
      }else{
        p(0);
      }
      return 0;
    }

    set<ll> se;;
    for(int i=0; i<L; i++){
      if(A[i+M]>=M){
        // iで見つけた
        ll j = i+M-1; // 検索後の後端
        se.insert(j);
        i = i+M-2;
      }
    }

    // BOTに見つからない文字列を具体的に作るならこれ
    // rep(i, L){
    //   if(se.count(i)>0){
    //     cout << '.';
    //   }
    //   cout << s[i];
    // }
    // cout << endl;

    p(se.size());
    
    return 0;
}