Pagini recente » Cod sursa (job #1527283) | Cod sursa (job #1192223) | Cod sursa (job #3292262) | Cod sursa (job #1906723) | Cod sursa (job #1829194)
#include <cstdio>
#include <cstring>
#define Nmax 2000003
using namespace std;
char search1[Nmax],pattern[Nmax];
int sufix[130],sol[1000],lim;
void sufix_creation()
{
int i = 0, j = 1;
while( j != strlen(pattern))
{
if(pattern[i] == pattern[j])
{
sufix[j] = i + 1;
i++;
j++;
}
else
{
while(pattern[i] != pattern[j] && i != 0)
i--;
if(pattern[i] != pattern[j])
{
sufix[j] = 0;
j++;
}
else
{
sufix[j] = sufix[i];
j++;
i++;
}
}
}
}
void read()
{
freopen("kmp.in","r",stdin);
freopen("kmp.out","w",stdout);
scanf("%s %s",&pattern,&search1);
sufix_creation();
}
void kmp()
{
int j = 0;
for(int i = 0 ; i < strlen(search1); i++)
{
if(pattern[j] == search1[i])
j++;
else
j = sufix[j];
if(j == strlen(pattern))
{
sol[lim++]= i - j + 1;
j = sufix[j - 1];
if(lim > 1000)
break;
}
}
}
void afisare()
{
printf("%d\n",lim);
for(int i= 0 ; i< lim ; i++)
printf("%d ",sol[i]);
}
int main()
{
read();
kmp();
afisare();
return 0;
}