Pagini recente » Cod sursa (job #2481606) | Cod sursa (job #2796539) | Cod sursa (job #1943892) | Cod sursa (job #987126) | Cod sursa (job #792789)
Cod sursa(job #792789)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2222222],b[2222222];
int t[2222222],rez[2222222];
int k,pos,i,l,nr;
int main()
{
in.getline(a,2222222);
in.getline(b,2222222);
t[0]=-1;
t[1]=0;
k=0;
pos=2;
l=2;
while(a[pos])
{
if(a[pos-1]==a[k])
{
t[pos]=++k;
pos++;
}
else
{
if(k!=0)
k=t[k];
else
t[pos++]=0;
}
++l;
}
--l;
//for(i=0;a[i];++i)
// out<<t[i]<<" ";
k=0;
pos=0;
while(b[pos])
{
if(b[pos]==a[k])
{
if(l==k)
{
rez[++nr]=pos-k;
k=t[k];
}
else
{
k++;
pos++;
}
}
else
{
if(k==0)
{
pos++;
continue;
}
k=t[k];
}
}
out<<nr<<"\n";
for(i=1;i<=nr;++i)
out<<rez[i]<<" ";
return 0;
}