Pagini recente » Cod sursa (job #1308015) | Cod sursa (job #1349103) | Cod sursa (job #212657) | Cod sursa (job #3179893) | Cod sursa (job #1910387)
#include <bits/stdc++.h>
using namespace std;
int pi[2000001], sol[1<<10], l = 0;
char a[2000001], b[2000001];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m;
f >> (a+1) >> (b+1);
int i, k = 0;
n = strlen(a+1);
m = strlen(b+1);
pi[1] = 0;
for(i=2; i<=n; i++){
while(k && a[k+1] != a[i])
k = pi[k];
if(a[k+1] == a[i])
k++;
pi[i] = k;
}
k = 0;
for(i=1; i<=m; i++){
while(k && a[k+1] != b[i])
k = pi[k];
if(a[k+1] == b[i])
k++;
if(k == n){
k = pi[n];
++l;
if(l<=1000){
sol[l] = i-n;
}
}
}
g << l << "\n";
l = min(l, 1000);
for(i=1; i<=l; i++)
g << sol[i] << " ";
g << "\n";
}