Pagini recente » Cod sursa (job #2335259) | Cod sursa (job #709278) | Cod sursa (job #2612559) | Cod sursa (job #1782296) | Cod sursa (job #1836015)
#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
{
int ok = 0 ;
while( i >= 0 && pattern[i] != pattern[j])
{
i--;
if(pattern[i] == pattern[j])
ok = 1;
}
if(ok == 1)
sufix[j] = i+1;
else
{
sufix[j] = 0;
}
i++;
j++;
}
}
}
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;
}