Pagini recente » Cod sursa (job #1894376) | Cod sursa (job #221931) | Cod sursa (job #791841) | Cod sursa (job #1396165) | Cod sursa (job #508675)
Cod sursa(job #508675)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int P = 2000000007/29;
const int N = 2000005;
const int B = 29;
int x, y, val;
int nr,n,m;
int sol[1005];
char a[N], b[N];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s",&a,&b);
int i, j ,sw, k;
n = strlen( a );
m = strlen( b );
// while(!( (a[n]>='a'&&a[n]<='z')||(a[n]>='A'&&a[n]<='Z')||(a[n]>='0'&&a[n]<='9') ) ) --n;
// while(!( (b[m]>='a'&&b[m]<='z')||(b[m]>='A'&&b[m]<='Z')||(b[m]>='0'&&b[m]<='9') ) ) --m;
for( i = 0;i < n; ++i)
x =( ( x * B ) % P + a[i] ) % P;
val = 1;
for( i = 1;i <= n-1; ++i)
val = (val * B) % P;
for( i = 0 ;i < n; ++i)
y = ( (y * B ) % P + b[i] ) % P;
b[m]='0';
for( i = n;i <= m ; ++i) {
if( x == y ) {
sw = 1;
for(j = i-1, k = n - 1;k >=0 ; --k, --j)
if( b[j] != a[k] ) {
sw = 0;
break;
}
if( sw ) {
++nr;
if(nr <= 1000)
sol[nr] = i - n;
}
}
y = ( y + P -( val *( b[i - n] ) )% P ) % P;
y = ( ( y * B ) % P + b[i] ) % P;
}
printf("%d\n" ,nr);
for(i = 1;i <=min(nr,1000); ++i)
printf("%d ", sol[i]);
return 0;
}