Pagini recente » Cod sursa (job #2937309) | Cod sursa (job #2539483) | Cod sursa (job #2442573) | Cod sursa (job #891972) | Cod sursa (job #1499055)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <stdio.h>
using namespace std;
char text[2000020],ss[2000020];
int P[2000020],m,n;
void citire()
{
freopen("strmatch.in","r",stdin);
fgets(ss,sizeof(ss),stdin);
fgets(text,sizeof(text),stdin);
m=strlen(ss)-1;
n=strlen(text)-1;
for(int i=strlen(ss);i>=0;i--)
ss[i+1]=ss[i];
for(int i=strlen(text);i>=0;i--)
text[i+1]=text[i];
ss[0]=' ';
text[0]=' ';
}
void prefix()
{
int a=0;
for(int i=2;i<=m;i++)
{
while(a && ss[a+1]!=ss[i])
a=P[a];
if(ss[i]==ss[a+1])
a++;
P[i]=a;
}
}
vector <int> sol;
int cont;
void cautare()
{
for(int i=1,k=0;i<=n;i++)
{
while(k && text[i]!=ss[k+1])
k=P[k];
if(text[i]==ss[k+1])
k++;
if(k==m)
{
k=P[k];
cont++;
if(cont<1000)
sol.push_back((i-m));
}
}
freopen("strmatch.out","w",stdout);
printf("%d\n",cont);
for(int i=0;i<min(cont,1000);i++)
printf("%d ",sol[i]);
}
int main()
{
citire();
prefix();
cautare();
return 0;
}