【題解】HDU 2203 亲和串

【題目敘述】https://vjudge.net/problem/HDU-2203
【解題想法】KMP (Knuth–Morris–Pratt algorithm)

  • 給定兩個字串 s1, s2,先把 s1 複製一份串接在自身後面。
  • 利用 KMP 判斷 s2 是否為 s1 的substring。
#include <iostream>
#include <vector>
using namespace std;

vector<int> build(string &t) {
    vector<int> F(t.size());
    F[0] = -1;
     
    for (int i = 1, pos = -1 ; i < t.size() ; i++) {
        while (~pos && t[i] != t[pos + 1])
            pos = F[pos];
 
        if (t[i] == t[pos + 1])
            pos++;
 
        F[i] = pos;
    }
    return F;
}

bool match(string &s, string &t, vector<int> &F) {
    for (int i = 0, pos = -1 ; i < s.size() ; i++) {
        while (~pos && s[i] != t[pos + 1])
            pos = F[pos];
 
        if (s[i] == t[pos + 1])
            pos++;
         
        if (pos + 1 == (int)t.size())
            return true;
    }
    return false;
}

int main(){
    string s1, s2;
    while (cin >> s1 >> s2){
        s1 = s1 + s1;
        vector <int> F;
        F = build(s2);
        if (match(s1, s2, F)){
            cout << "yes\n";
        } else {
            cout << "no\n";
        }
    }
}
分享本文 Share with friends