Pagini recente » Cod sursa (job #1683910) | Cod sursa (job #2448190) | Cod sursa (job #2145561) | Cod sursa (job #2422255) | Cod sursa (job #508666)
Cod sursa(job #508666)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int P = 1000000007;
const int N = 2000005;
const int B = 73;
int x, y, n, val, m;
int sol[1005],nr;
char a[N], b[N];
typedef long long ll;
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s",&a,&b);
int i, j ,sw, k;
long long w;
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)
w=( ll )x * B, x =( w % P + a[i] ) % P;
val = 1;
for( i = 1;i <= n-1; ++i)
w=(ll)val*B,val = w % P;
for( i = 0 ;i < n; ++i)
w=(ll)y*B, y = ( w % 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;
}
}
w=(ll) val * b[i-n], y = ( y + P -( w % P ) ) % P;
w=(ll) y*B, y = ( w % P + b[i] ) % P;
}
printf("%ld\n" ,nr);
for(i = 1;i <=min(nr,1000); ++i)
printf("%ld ", sol[i]);
return 0;
}