Cod sursa(job #1328169)

Utilizator theprdvtheprdv theprdv Data 28 ianuarie 2015 04:12:14
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
// Rabin Karp (2 bases)
#include <fstream>
#include <string.h>
using namespace std;

fstream fin("strmatch.in", ios::in);
fstream fout("strmatch.out", ios::out);

#define MAX 2000005
#define MOD1 100007
#define MOD2 100021
#define base1 27
#define base2 29

char N[MAX], M[MAX], sub[MAX];
int n, m;
int p_hash1, p_hash2, s_hash1, s_hash2, sol[MAX];

int pow(int n, int exp){
    int result=1;
    for(int i=1; i<=exp; i++)
        result*=n;
    return result;
}

int main()
{
    fin.getline(N, MAX);    n=strlen(N);
    fin.getline(M, MAX);    m=strlen(M);

    for(int i=0; i<n; i++)
        p_hash1+=N[i]*pow(base1, n-(i+1))%MOD1,
        p_hash2+=N[i]*pow(base2, n-(i+1))%MOD2;
    for(int i=0; i<n; i++)
        s_hash1+=M[i]*pow(base1, n-(i+1))%MOD1,
        s_hash2+=M[i]*pow(base2, n-(i+1))%MOD2;

    if(p_hash1==s_hash1 && p_hash2==s_hash2)
        sol[++sol[0]]=1;
    else {
        for(int i=0; i<m-n; i++){
            s_hash1=((s_hash1-M[i]*pow(base1, n-1))*base1+M[n+i])%MOD1,
            s_hash2=((s_hash2-M[i]*pow(base2, n-1))*base2+M[n+i])%MOD2;

            if(s_hash1==p_hash1 && p_hash2==s_hash2)
            {
                sol[0]++;
                if(sol[0]<=1000) sol[sol[0]]=i+1;
            }
        }
    }
    fout<<sol[0]<<"\n";
    for(int i=1; i<=sol[0]; i++)
        fout<<sol[i]<<" ";

    fin.close();
    fout.close();
    return 0;
}