Cod sursa(job #1073116)

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