Pagini recente » Cod sursa (job #1850104) | Cod sursa (job #922510) | Cod sursa (job #1822455) | Cod sursa (job #1257578) | Cod sursa (job #2808334)
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
int lps[2000003], i, n, m, k, j, l, len, v[2000005], cnt;
string pat, text;
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> pat;
cin >> text;
lps[0] = 0;
n = pat.size();
len = 0;
i = 1;
while (i < n) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
m = text.size();
i = 0;
while (i < m) {
if (pat[j] == text[i]) {
i++;
j++;
}
if (j == n) {
v[++cnt] = i - n;
j = lps[j - 1];
}
else if (pat[j] != text[i] and i<m) {
if (j != 0) j = lps[j - 1];
else i++;
}
}
cout << cnt << '\n';
if (cnt > 1000) cnt = 1000;
for (i = 1;i <= cnt;i++)
cout << v[i] << " ";
}