Pagini recente » Cod sursa (job #515276) | Cod sursa (job #3180369) | Cod sursa (job #2244210) | Cod sursa (job #1965296) | Cod sursa (job #921561)
Cod sursa(job #921561)
#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;
int dim;
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]){
if(dim<1000)
potriv.push_back(i-d[0]);
++dim;
k=pi[k];
}
}
}
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",dim);
for(int i=0;i<potriv.size();++i)
printf("%d ",potriv[i]);
}
int main()
{
citire();
kmp();
afisare();
return 0;
}