Pagini recente » Cod sursa (job #1192279) | Cod sursa (job #2246483) | Cod sursa (job #2007812) | Cod sursa (job #1041244) | Cod sursa (job #614880)
Cod sursa(job #614880)
#include <fstream>
#include <string.h>
inline int min(int a, int b)
{
return (a<b?a:b);
}
using namespace std;
char s[2000000],a[2000000];
int p[2000000],i,j,m,n,k,sol[1002],ns;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>(a+1)>>(s+1);
n=strlen(a+1);
m=strlen(s+1);
for(i=2;i<=n;i++)
{
k=p[i-1]+1;
if( a[k] != a[i] ) k=p[k]+1;
if( a[k] == a[i] ) p[i]=k;
else p[i]=0;
}
k=0;
ns=0;
for(i=1;i<=m+1;i++)
{
while( k>0 && s[i] != a[k+1] ) k=p[k];
if( a[k+1] == s[i] ) ++k;
if( k == n )
{
if(ns<999)sol[ns]=i-k;
ns++;
k=p[k];
}
}
g<<ns<<"\n";
for(i=0;i<min(1000,ns);i++) g<<sol[i]<<" ";
return 0;
}