Pagini recente » Cod sursa (job #1434519) | Cod sursa (job #1559681) | Cod sursa (job #2070786) | Cod sursa (job #233211) | Cod sursa (job #555461)
Cod sursa(job #555461)
#include<fstream>
#define dmax 2000003
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n,m,pi[dmax],q,nr, sol[dmax];
char t[dmax], p[dmax];
void prefix()
{
int i,k;
pi[1]=0;
k=0;
for(i=2;i<=m;i++)
{
while( p[i] != p[k+1] && k>0 )
k=pi[k];
if(p[i] == p[k+1])
k++;
pi[i] = k;
}
}
int main()
{
int i;
in>>p>>t;
in.close();
n=strlen(t);
m=strlen(p);
for(i=n; i>0 ;i--)
t[i] = t[i-1];
for(i=m; i>0 ;i--)
p[i] = p[i-1];
prefix();
q=0;
for(i=1;i<=n;i++)
{
while(t[i] != p[q+1] && q>0)
q = pi[q];
if(t[i] == p[q+1])
q++;
if(q==m)
{ nr++;
if(nr <= 1000)
sol[nr] = i-q;
}
}
out<<nr<<'\n';
for(i=1;i<=nr;i++)
out<<sol[i]<<" ";
out.close();
return 0;
}