Pagini recente » Cod sursa (job #2084796) | Cod sursa (job #1155787) | Cod sursa (job #776796) | Cod sursa (job #895436) | Cod sursa (job #1499047)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <stdio.h>
using namespace std;
char text[2000020],ss[2000020];
int P[2000020];
void citire()
{
freopen("strmatch.in","r",stdin);
fgets(ss,sizeof(ss),stdin);
fgets(text,sizeof(text),stdin);
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<strlen(ss);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<=strlen(text)-1;i++)
{
while(k && text[i]!=ss[k+1])
k=P[k];
if(text[i]==ss[k+1])
k++;
if(k>=strlen(ss)-2)
{
cont++;
sol.push_back((i-k));
}
}
freopen("strmatch.out","w",stdout);
printf("%d\n",cont);
for(int i=0;i<cont;i++)
printf("%d ",sol[i]);
}
int main()
{
citire();
prefix();
cautare();
return 0;
}