Pagini recente » Cod sursa (job #2597734) | Cod sursa (job #1881077) | Cod sursa (job #3276212) | Cod sursa (job #2864373) | Cod sursa (job #920376)
Cod sursa(job #920376)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N=2000100;
char sub[N],str[N];
int pi[N];
int d[2];
vector <int> potriv;
void prefix()
{
int k=0;
pi[1]=0;
for(int i=2;i<=d[0];++i)
{
while(k>0&&sub[k+1]!=sub[i])
k=pi[k];
if(sub[k+1]==sub[i])
++k;
pi[i]=k;
}
}
void kmp()
{
prefix();
int k=0;
for(int i=1;i<=d[1];++i)
{
while(k>0&&sub[k+1]!=str[i])
k=pi[k];
if(sub[k+1]==str[i])
++k;
if(k==d[0])
potriv.push_back(i-d[0]);
if(potriv.size()==1000)
return;
}
}
void citire()
{
freopen("strmatch.in","r",stdin);
gets(sub+1);
d[0]=strlen(sub+1);
gets(str+1);
d[1]=strlen(str+1);
}
void afisare()
{
freopen("strmatch.out","w",stdout);
printf("%d\n",potriv.size());
for(int i=0;i<potriv.size();++i)
printf("%d ",potriv[i]);
}
int main()
{
citire();
kmp();
afisare();
return 0;
}