Pagini recente » Cod sursa (job #2767258) | Cod sursa (job #2222842) | Cod sursa (job #2921731) | Cod sursa (job #1669799) | Cod sursa (job #1073085)
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int MAX_LEN = 2000000;
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;
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 = int_mod((hashA * BASE) + A[i], MOD);
hashA2 = int_mod((hashA2 * BASE) + A[i], MOD2);
if(i!=0){
roll_powah = int_mod(roll_powah * BASE, MOD);
roll_powah2 = int_mod(roll_powah2 * BASE, MOD2);
}
}
for(int i = 0 ; i < lenA; ++i){
hashS = int_mod((hashS * BASE) + B[i], MOD);
hashS2= int_mod((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 = int_mod(hashS * BASE + B[i],MOD);
hashS2 = int_mod(hashS2 - int_mod(B[i-lenA] * roll_powah2,MOD2),MOD2);
hashS2 = int_mod(hashS2 * BASE + B[i],MOD2);
if(hashS == hashA && hashS2 == hashA2){
ans[ansNo++] = i - lenA+1;
}
}
cout << ansNo << endl;
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;
}