Pagini recente » Cod sursa (job #1942163) | Cod sursa (job #1918134) | Cod sursa (job #1564861) | Cod sursa (job #1770910) | Cod sursa (job #1836593)
#include <cstring>
#include <cstdio>
#define Nmax 2000005
#include <vector>
using namespace std;
char sir[Nmax];
char pattern[Nmax];
vector <int> solutie;
int sufix[Nmax];
int lim1,lim2;
void prepare()
{
int i = 0 , j = 1;
while(j < lim1)
{
if(pattern[i] == pattern[j])
{
sufix[j] = i +1;
i++;
j++;
}
else
{
if(i > 0)
i = sufix[i-1];
else
{
sufix[j] = 0;
j++;
i=0;
}
}
}
}
void kmp()
{
int j = 0 ;
for(int i = 0 ; i < lim2; i++)
{
while( j > 0 && sir[i] != pattern[j])
j = sufix[j-1];
if(pattern[j] == sir[i])
j++;
if(j == lim1)
solutie.push_back(i- j + 1);
}
}
void afisare()
{
printf("%d\n",solutie.size());
int lim = solutie.size();
for(int i = 0 ; i < lim ; i++)
printf("%d ",solutie[i]);
}
void read()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&pattern,&sir);
lim1= strlen(pattern);
lim2= strlen(sir);
prepare();
kmp();
}
int main()
{
read();
afisare();
return 0;
}