Cod sursa(job #1362823)

Utilizator somuBanil Ardej somu Data 26 februarie 2015 15:50:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <cmath>
#define mod1 666013
#define mod2 100007

using namespace std;

string P, S;
int lenS, lenP, pattern1, pattern2, num1, num2, P1, P2, k;
int sol[1005];

int main() {
    
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    
    fin >> P;
    fin >> S;
    
    lenP = int(P.size());
    lenS = int(S.size());
    
    if (lenP > lenS) {
        fout << 0 << "\n";
        return 0;
    }
    
    pattern1 = pattern2 = 0;
    P1 = P2 = 1;
    
    for (int i = 0; i < lenP; i++) {
        pattern1 = (pattern1 * 26 + P[i]) % mod1;
        pattern2 = (pattern2 * 27 + P[i]) % mod2;
        if (i > 0)
            P1 = (P1 * 26) % mod1,
            P2 = (P2 * 27) % mod2;
    }
    
    num1 = num2 = 0;
    
    for (int i = 0; i < lenP; i++) {
        num1 = (num1 * 26 + S[i]) % mod1;
        num2 = (num2 * 27 + S[i]) % mod2;
    }
    
    k = 0;
    if (pattern1 == num1 && pattern2 == num2)
        sol[++k] = 0;
    
    for (int i = lenP; i < lenS; i++) {
        num1 = (((num1 - (P1 * S[i - lenP])) % mod1 + mod1) * 26 + S[i]) % mod1;
        num2 = (((num2 - (P2 * S[i - lenP])) % mod2 + mod2) * 27 + S[i]) % mod2;
        if (num1 == pattern1 && num2 == pattern2) {
            k++;
            if (k <= 1000)
                sol[k] = i - lenP + 1;
        }
    }
    
    fout << k << "\n";
    for (int i = 1; i <= min(k, 1000); i++)
        fout << sol[i] << " ";
    
    fin.close();
    fout.close();
    
    return 0;
}