Pagini recente » Cod sursa (job #2774662) | Cod sursa (job #450370) | Cod sursa (job #466136) | Cod sursa (job #377313) | Cod sursa (job #508662)
Cod sursa(job #508662)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll P = 1000000007;
const ll N = 2000005;
const ll B = 173;
ll x, y, n, val, m;
ll sol[1005],nr;
char a[N], b[N];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s",&a,&b);
long long 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'-1;
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;
}
// printf("%lld \n",i-n);
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("%lld\n" ,nr);
for(i = 1;i <=min(nr,1000ll); ++i)
printf("%lld ", sol[i]);
return 0;
}