Pagini recente » Cod sursa (job #2229506) | Cod sursa (job #2030970) | Cod sursa (job #3130195) | Cod sursa (job #432905) | Cod sursa (job #3158415)
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001], b[2000001];
int la, lb;
int lps[2000001];
int ans;
int pos[1001];
int main() {
fin >> a >> b;
la = strlen(a), lb = strlen(b);
for (int i = la; i>=1; i--) {
a[i] = a[i-1];
}
a[0] = ' ';
for (int i = lb; i>=1; i--) {
b[i] = b[i-1];
}
b[0] = ' ';
lps[1] = 0;
int j = 0;
for (int i = 2; i<=la; i++) {
while (j && a[j+1] != a[i]) {
j = lps[j];
}
if (a[j+1] == a[i]) {
j++;
}
lps[i] = j;
}
j = 0;
for (int i = 1; i<=lb; i++) {
while (j && a[j+1] != b[i]) {
j = lps[j];
}
if (a[j+1] == b[i]) {
j++;
}
if (j == la) {
j = lps[la];
ans++;
if (ans <= 1000) {
pos[ans] = i-la;
}
}
}
fout << ans << '\n';
for (int i = 1; i<=min(ans, 1000); i++) {
fout << pos[i] << " ";
}
return 0;
}