Pagini recente » Cod sursa (job #1002834) | Cod sursa (job #2823670) | Cod sursa (job #3141158) | Cod sursa (job #1901016) | Cod sursa (job #1542329)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int z[2000005],sol[2000005],st,dr,cate,sir,nr,este;
char s[2000005],v[2000005];
int minim ( int a , int b ){
if ( a > b )
return a;
return b;
}
int main()
{
fin.getline( s , 2000005 );
cate=strlen(s);
fin.getline( v , 2000005 );
s[cate+1]='*';
strcat( s , "*" );
strcat( s , v );
st=-1;
dr=-1;
nr=strlen(s);
for ( int i=1 ; i<=nr-1 ; i++ ){
if ( i <= dr )
z[i]=minim(dr-i+1,z[i-st]);
while ( s[z[i]]==s[i+z[i]] )
z[i]=z[i]+1;
if ( i+z[i]-1 > dr ){
dr=i+z[i]-1;
st=i;
}
}
for ( int i=0 ; i<=nr-1 ; i++ ){
if ( z[i]==cate ){
sol[i]=1;
este++;
}
}
fout<<este<<'\n';
for ( int i=1 ; i<=nr-1 ; i++ ){
if ( sol[i]==1 )
fout<<i-cate-1<<' ';
}
}