Cod sursa(job #1073085)

Utilizator xoSauceSergiu Ferentz xoSauce Data 5 ianuarie 2014 17:21:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#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;
}