Pagini recente » Cod sursa (job #990025) | Cod sursa (job #628503) | Cod sursa (job #1032946) | Cod sursa (job #702238) | Cod sursa (job #2288938)
#include <fstream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
FILE*f=fopen("strmatch.in","r");
FILE*g = fopen("strmatch.out","w");
char A[2000002],B[2000002];
int k=0,n,m;
vector<int>poz;
int P[2000002];
int main()
{
fscanf(f,"%s",A+1);
fscanf(f,"%s",B+1);
n=strlen(A+1);
m=strlen(B+1);
if(n>m)
{
fprintf(g,"0");
return 0;
}
for(int i=2;i<=n;++i)
{
for(;k>0 && A[k+1]!=A[i];)k=P[k];
if(A[k+1]==A[i])k++;
P[i]=k;
}
k=0;
for(int i=1;i<=m;++i)
{
for(;k!=0 && A[k+1]!=B[i];)k=P[k];
if(A[k+1]==B[i])k++;
if(k==n)
{
poz.push_back(i-n);
k=P[k];
}
}
fprintf(g,"%d\n",poz.size());
for(int i=0;i<poz.size() && i<1000;++i)
{
fprintf(g,"%d ",poz[i]);
}
return 0;
}