Pagini recente » Cod sursa (job #3167142) | Cod sursa (job #739202) | Cod sursa (job #417131) | Cod sursa (job #2580684) | Cod sursa (job #1967788)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define dim 2000000
char a[dim + 2], b[dim + 2];
int pi[dim + 2], pos[dim + 2], nrpos;
int main() {
f >> (a + 1) >> (b + 1);
int m = strlen(a + 1), n = strlen(b + 1);
int k = 0;
for(int i = 2;i <= m;i++) {
while(k && a[k + 1] != a[i])
k = pi[k];
if(a[k + 1] == a[i])
k++;
pi[i] = k;
}
k = 0;
for(int i = 1;i <= n;i++) {
while(k && a[k + 1] != b[i])
k = pi[k];
if(a[k + 1] == b[i])
k++;
if(k == m) {
pos[++nrpos] = i - m;
k = pi[m];
}
}
g << nrpos << "\n";
for(int i = 1;i <= min(nrpos, 1000);i++)
g << pos[i] << " ";
f.close(), g.close();
return 0;
}