【題目敘述】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";
}
}
}