Pagini recente » Cod sursa (job #819017) | Cod sursa (job #1620841) | Cod sursa (job #2164298) | Cod sursa (job #2360747) | Cod sursa (job #2306468)
#include <bits/stdc++.h>
using namespace std;
vector <int> compute_lps(string pattern) {
int m = (int)pattern.length();
vector <int> lps (m);
lps[0] = 0;
for (int i = 1; i < m; ++ i) {
int j = lps[i-1];
while (j > 0 && pattern[i] != pattern[j]) {
j = lps[j];
}
if (pattern[i] == pattern[j]) ++ j;
lps[i] = j;
}
return lps;
}
void KMP(string pattern, string text){
int n = (int)text.length();
int m = (int)pattern.length();
vector <int> lps = compute_lps(pattern);
int i = 0, j = 0, app = 0, pos[1002];
while (i < n) {
while (j < m && i < n && text[i] == pattern[j])
i++, j++;
if (j == m && app < 1e3) {
pos[app] = i - m;
app ++;
j = lps[j-1];
}
else if(i < n && pattern[j] != text[i]){
if(j != 0)
j = lps[j-1];
else ++i;
}
}
printf("%d\n", app);
for(int i = 0; i < app; ++ i)
printf("%d ", pos[i]);
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string text;
string pattern;
cin >> pattern;
cin >> text;
KMP(pattern, text);
return 0;
}