1 条题解
-
0Empire-003 LV 7 @ 2017-10-15 23:21:00
//简单Sunday算法 //参考资料https://www.61mon.com/index.php/archives/213/ #include <bits/stdc++.h> using namespace std; const int MAX_CHAR = 256; const int MAX_LENGTH = 1000; void GetNext(string & p, int m, int next[]) { for(int i = 0; i < MAX_CHAR; i++) next[i] = -1; for(int i = 0; i < m; i++) next[p[i]] = i; } void Sunday(string & s, int n, string & p, int m) { int next[MAX_CHAR]; GetNext(p, m, next); int i = 0, j, k; while(i <= n - m) { j = i; k = 0; while(j < n && k < m && s[j] == p[k]) j++, k++; if(k == m) cout << i+m << endl; if(i + m < n) i += (m - next[s[i + m]]); else return ; } } int main() { string s, p; int n, m; while(cin >> s >> p) { n = s.size(); m = p.size(); Sunday(s, n, p, m); cout << endl; } return 0; }
- 1