Pagini recente » Cod sursa (job #1800511) | Cod sursa (job #855205) | Cod sursa (job #2334644) | Cod sursa (job #591683) | Cod sursa (job #2277185)
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000000],b[2000000];
int ans1[2000000],c[2000000];
int main()
{
char h;
in>>a;
in>>b;
in.get(h);
int q=0,n,l,ans=0;
n = strlen(b);
l = strlen(a);
c[1] = 0;
for ( int i = 0 ; i <= n ; i++ ){
while ( q && b[i-1] != a[q] )
q = c[q];
if ( b[ i - 1 ] == a [ q ] )
q++;
c[i] = q;
}
for ( int i = 0 ; i <= n - 1 ; i++ ){
while ( q && b[i-1] != a[q] )
q = c[q];
if ( b[ i - 1 ] == a [ q ] )
q++;
if ( q == l ){
q = c[l];
ans++;
ans1[i-l] = 1;
}
}
out<<ans<<'\n';
for ( int i = 1 ; i <= n ; i++ ){
if ( ans1[i] != 0 )
out<<i<<" ";
}
return 0;
}