Pagini recente » Cod sursa (job #2414219) | Cod sursa (job #2266633) | Cod sursa (job #596166) | Cod sursa (job #131054) | Cod sursa (job #1073116)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int MAX_LEN = 2000001;
char A[MAX_LEN];
char B[MAX_LEN];
int int_mod(int x,int m)
{
return (x%m+m)%m;
}
int ans[1050];
void solve(char A[], char B[]){
int lenA = strlen(A);
int lenB = strlen(B);
const int BASE = 257;
const int MOD = 8355967;
const int MOD2 = 1000001;
if(lenA > lenB)
{
cout << 0 << endl;
return;
}
int hashA = 0;
int hashA2 = 0;
int hashS = 0;
int hashS2= 0;
int ansNo = 0;
int roll_powah = 1; // power of term to subtract
int roll_powah2 = 1;
for(int i = 0 ; i < lenA ; ++i)
{
hashA = ((hashA * BASE) + A[i]) % MOD;
hashA2 = ((hashA2 * BASE) + A[i]) % MOD2;
if(i!=0){
roll_powah = roll_powah * BASE % MOD;
roll_powah2 = roll_powah2 * BASE % MOD2;
}
}
for(int i = 0 ; i < lenA; ++i){
hashS = ((hashS * BASE) + B[i]) % MOD;
hashS2= ((hashS2 * BASE) + B[i]) % MOD2;
}
if(hashS == hashA && hashA2 == hashS2){
ans[ansNo++] = 0;
}
for(int i = lenA; i < lenB; i++){
hashS = int_mod(hashS - int_mod(B[i-lenA] * roll_powah,MOD),MOD);
hashS = (hashS * BASE + B[i]) % MOD;
hashS2 = int_mod(hashS2 - int_mod(B[i-lenA] * roll_powah2,MOD2),MOD2);
hashS2 = (hashS2 * BASE + B[i])%MOD2;
if(hashS == hashA && hashS2 == hashA2){
ans[ansNo++] = i - lenA+1;
if(ansNo > 1001)
break;
}
}
cout << ansNo << endl;
ansNo = (ansNo > 1000)?1000:ansNo;
for(int i = 0; i < ansNo ; i++){
cout << ans[i] << " ";
}
cout << endl;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",A,B);
solve(A,B);
return 0;
}