Pagini recente » Cod sursa (job #2308251) | Cod sursa (job #1879784) | Cod sursa (job #1434421) | Cod sursa (job #1646779) | Cod sursa (job #508428)
Cod sursa(job #508428)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int P = 1000000000;
const int N = 2000005;
const int B = 29;
int x, y, n, val, m;
int sol[1005],nr;
char a[N], b[N];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(a, N, stdin);
fgets(b, N, stdin);
int i, j ,sw, k;
n = strlen( a );--n;
m = strlen( b );--m;
for( i = 0;i < n; ++i)
k=a[i]-'A'+1,x =( ( x * B ) % P + k ) % P;
val = 1;
for( i = 1;i <= n-1; ++i)
val = (val * B) % P;
for( i = 0 ;i < n; ++i)
k = b[i] - 'A' + 1, y = ( (y * B ) % P + k ) % 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] - 'A' + 1) ) % P;
y = ( ( y * B ) % P + b[i]-'A' + 1 ) % P;
}
printf("%ld\n" ,nr);
for(i = 1;i <=min(nr,1000); ++i)
printf("%ld ", sol[i]);
return 0;
}