Pagini recente » Cod sursa (job #2652268) | Cod sursa (job #1849959) | Cod sursa (job #3173051) | Cod sursa (job #2620662) | Cod sursa (job #932586)
Cod sursa(job #932586)
#include<algorithm>
#include<cstdio>
#include<fstream>
#include<cstring>
#define NM 2000005
using namespace std;
char a[NM], b[NM];
int pr[NM];
int main()
{
int i, j, n, m, r, nr = 0,poz[1005];
ifstream f ("strmatch.in");
f>>a>>b;
n = strlen(a), m = strlen(b);
j = 0;
pr[1] = 0;
for(i = 2; i <= n; i++)
{
while ( j>0 && a[j] != a[i-1])
j = pr[j];
if(a[j]==a[i-1])
j++;
pr[i] = j;
}
freopen("strmatch.out", "w", stdout);
r = 0;
for(i = 1; i<=m; i++)
{
while( r>0 && b[i-1] != a[r])
r = pr[r];
if(b[i-1] == a[r])
r++;
if(r == n)
{
r = pr[r],nr++;
if(nr <=1000) poz[nr] = i - n;
}
}
printf("%i\n", nr);
for(i = 1; i<= min(nr, 1000); i++)
printf("%i ", poz[i]);
return 0;
}