Cod sursa(job #1343359)

Utilizator somuBanil Ardej somu Data 15 februarie 2015 13:33:20
Problema Potrivirea sirurilor Scor 64
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define mod1 100007
#define mod2 100021

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string S, P;
int P1, P2, hashA1, hashA2, hash1, hash2, lp, ls;
int sol[1005];

void read() {
    fin >> P >> S;
    lp = int(P.size());
    ls = int(S.size());
}

void solve() {
    
    P1 = P2 = 1;
    hashA1 = hashA2 = 0;
    for (int i = 0; i < lp; i++)
    {
        hashA1 = (hashA1 * 26 + P[i]) % mod1;
        hashA2 = (hashA2 * 27 + P[i]) % mod2;
        
        if (i != 0)
            P1 = (P1 * 26) % mod1,
            P2 = (P2 * 27) % mod2;
    }
    
    if (lp > ls) {
        cout << 0 << "\n";
        return;
    }
    
    hash1 = hash2 = 0;
    for (int i = 0; i < lp; i++) {
        hash1 = (hash1 * 26 + S[i]) % mod1;
        hash2 = (hash2 * 27 + S[i]) % mod2;
    }
    
    int rez = 0;
    if (hash1 == hashA1 && hash2 == hashA2) {
        sol[++rez] = 1;
    }
    
    for (int i = lp; i < ls; i++) {
        
        hash1 = (((hash1 - (S[i - lp] * P1)) % mod1 + mod1) * 26 + S[i]) % mod1;
        hash2 = (((hash2 - (S[i - lp] * P2)) % mod2 + mod2) * 27 + S[i]) % mod2;
        
        if (hash1 == hashA1 && hash2 == hashA2) {
            ++rez;
            if (rez <= 1000)
                sol[rez] = i - lp + 1;
        }
    }
    
    fout << rez << "\n";
    
    for (int i = 1; i <= min(1000, rez); i++)
        fout << sol[i] << " ";
    fout << "\n";
    
}

int main() {
    
    read();
    solve();
    
    fin.close();
    fout.close();
    
    return 0;
}