Pagini recente » Cod sursa (job #1066852) | Cod sursa (job #328327) | Cod sursa (job #1706321) | Cod sursa (job #1194087) | Cod sursa (job #1793890)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int N = 2000010, M = 1010;
int n, k, i, j, z[2 * N], lena, lenb, p, sol[M];
char a[N], b[N], s[2 * N];
int main() {
fin >> a >> b;
lena = strlen(a) - 1;
lenb = strlen(b) - 1;
strcpy(s, "0");
strcat(s, a);
strcat(s, "#");
strcat(s, b);
n = strlen(s) - 1;
k = 1;
for (i = 2; i <= n; ++i) {
if (k + z[k] - 1 < i) {
p = i;
for (j = 1; p <= n && s[p] == s[j]; ++p, ++j);
z[i] = p - i;
k = i;
} else {
z[i] = min(z[i - k + 1], k + z[k] - i);
for (; z[i] + i <= n && s[z[i] + i] == s[z[i] + 1]; ++z[i]);
if (i + z[i] - 1 > k + z[k] - 1) {
k = i;
}
}
}
k = 0;
for (i = lena + 2; i <= n; ++i) {
if (z[i] > lena) {
k++;
if(k <= 1000)
sol[k] = i - lena - 3;
}
}
fout << k << "\n";
k = min(1000, k);
for (i = 1; i <= k; ++i) {
fout << sol[i] << " ";
}
return 0;
}