Pagini recente » Cod sursa (job #543546) | Cod sursa (job #1220946) | Cod sursa (job #907158) | Cod sursa (job #2777004) | Cod sursa (job #1073066)
#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;
if(lenA > lenB)
{
cout << 0;
return;
}
int hashA = 0;
int hashS = 0;
int ansNo = 0;
int roll_powah = 1; // power of term to subtract
for(int i = 0 ; i < lenA ; ++i)
{
hashA = int_mod((hashA * BASE) + A[i], MOD);
if(i!=0)
roll_powah = int_mod(roll_powah * BASE, MOD);
}
for(int i = 0 ; i < lenA; ++i){
hashS = int_mod((hashS * BASE) + B[i], MOD);
}
if(hashS == hashA){
ans[ansNo++] = 1;
}
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);
if(hashS == hashA){
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;
}