Pagini recente » Cod sursa (job #2747996) | Cod sursa (job #1655475) | Cod sursa (job #1012397) | Cod sursa (job #1926553) | Cod sursa (job #1955167)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[1000005], b[1000005];
int n, m, i, q, lg[1000005], sol[1005], ns;
int main() {
f.getline(a+1, sizeof(a));
f.getline(b+1, sizeof(b));
n = strlen(a+1), m = strlen(b+1);
for (i = 2; i <= n; i++) {
while (a[q+1] != a[i] && q)
q = lg[q];
if (a[q+1] == a[i]) q++;
lg[i] = q;
}
for (i = 1; i <= m; i++) {
while (a[q+1] != b[i] && q)
q = lg[q];
if (a[q+1] == b[i]) q++;
if (q == n) {
ns++;
if (ns<= 1000) sol[ns] = i-q;
q = lg[q];
}
}
g << ns << '\n';
ns= min(ns,1000);
for (i =1; i <= ns; i++) g << sol[i] << ' ';
return 0;
}