Pagini recente » Cod sursa (job #700039) | Cod sursa (job #1972587) | Cod sursa (job #770645) | Cod sursa (job #2205879) | Cod sursa (job #1836545)
#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; )
{
if(pattern[j] == sir[i])
{
j++;
i++;
}
else
{
if(j != 0)
j = sufix[i];
else
i++;
}
if(j == lim1)
{
if(solutie.size() == 1000)
return;
solutie.push_back(i - lim1);
i--;
j = 0;
}
}
}
void afisare()
{
printf("%d\n",solutie.size());
for(vector <int> :: iterator it = solutie.begin() ; it != solutie.end() ; it++)
printf("%d ",*it);
}
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;
}