Pagini recente » Cod sursa (job #165000) | Cod sursa (job #495246) | Cod sursa (job #405773) | Cod sursa (job #941249) | Cod sursa (job #696732)
Cod sursa(job #696732)
#include<stdio.h>
#include<vector>
#include<cstring>
#define Nmax 2000005
using namespace std;
char a[Nmax],b[Nmax];
int pi[Nmax],N,M;
void prefix()
{
int k=0,i;
pi[1] = 0;
for(i=2;i<=N;++i)
{
while(k>0 && a[k+1] != a[i])
k = pi[k];
if(a[k+1] == a[i])
k = k+1;
pi[i] = k;
}
}
int main()
{
FILE*f = fopen("strmatch.in","r");
fscanf(f,"%s %s",a,b);
fclose(f);
int k=0,i;
N = strlen(a);
M = strlen(b);
for(i=M;i>0;--i)b[i] = b[i-1];
for(i=N;i>0;--i)a[i] = a[i-1];
prefix();
vector<int> pos;
for(i=1;i<=M;++i)
{
while(k>0 && a[k+1] != b[i])
k = pi[k];
if(a[k+1] == b[i])
k = k+1;
if(k == N)
pos.push_back(i-N+1);
}
FILE*g = fopen("strmatch.out","w");
fprintf(g,"%d\n",pos.size());
k=0;
for(vector<int>::iterator it = pos.begin();it!=pos.end() && k<1000;++it)
{
fprintf(g,"%d ",*it-1);
++k;
}
fclose(g);
return 0;
}