Pagini recente » Istoria paginii runda/1234567/clasament | Cod sursa (job #2325342) | Cod sursa (job #1603175) | Cod sursa (job #1236916) | Cod sursa (job #1893704)
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#include <cmath>
#define MaxN 2000005
#define INF 2140000000
using namespace std;
FILE*IN,*OUT;
char first[MaxN],second[MaxN];
int Pref[MaxN],N=0,Out[MaxN],Len;
void Precalc_Pref()
{
Len=strlen(first+1);
int k=0;
for(int i=2;i<=Len;i++)
{
while(k&&first[k+1]!=first[i])
k=Pref[k];
if(first[k+1]==first[i])
k++;
Pref[i]=k;
}
}
void Precalc_D()
{
int L=strlen(second+1),k=0;
for(int i=1;i<=L;i++)
{
while(k&&first[k+1]!=second[i])
k=Pref[k];
if(first[k+1]==second[i])
k++;
if(k==Len)
Out[++N]=i-Len;
}
}
int main()
{
IN=fopen("strmatch.in","r");
OUT=fopen("strmatch.out","w");
fscanf(IN,"%s%s",first+1,second+1);
Precalc_Pref();
Precalc_D();
fprintf(OUT,"%d\n",N);
for(int i=1;i<=min(N,1000);i++)
fprintf(OUT,"%d ",Out[i]);
return 0;
}