Cod sursa(job #3236151)

Utilizator StefanStratonStefan StefanStraton Data 26 iunie 2024 14:48:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <cstring>

#define MOD1 100007
#define MOD2 100021

using namespace std;

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

char s1[2000001], s2[2000001];
int lgS1, lgS2;
int nrS1mod1, nrS1mod2, p1, p2, nrS2mod1, nrS2mod2;
char v[2000001];

int main(){
    in >> s1 >> s2;

    lgS1 = strlen(s1);
    lgS2 = strlen(s2);

    if (lgS1 > lgS2){
        out << 0; return 0;
    }
    else{
        p1 = p2 = 1;
        for(int i = 0; i < lgS1; i++){
            nrS1mod1 = (nrS1mod1 * 77 + s1[i])% MOD1;
            nrS1mod2 = (nrS1mod2 * 77 + s1[i])% MOD2;
            if (i!=0)
                p1 = (p1 * 77) % MOD1, p2 = (p2 * 77) % MOD2;
        }

        for (int i = 0; i < lgS1; i++){
            nrS2mod1 = (nrS2mod1 * 77 + s2[i]) % MOD1;
            nrS2mod2 = (nrS2mod2 * 77 + s2[i]) % MOD2;
        }
        int cnt = 0;
        if(nrS2mod1 == nrS1mod1 && nrS2mod2 == nrS1mod2){
            v[0] = 1;
            cnt++;
        }
        for(int i = lgS1; i < lgS2; i++){
            nrS2mod1 = ((nrS2mod1 - (s2[i-lgS1] * p1) % MOD1 + MOD1) * 77 + s2[i]) % MOD1;
            nrS2mod2 = ((nrS2mod2 - (s2[i-lgS1] * p2) % MOD2 + MOD2) * 77 + s2[i]) % MOD2;
            if(nrS2mod1 == nrS1mod1 && nrS2mod2 == nrS1mod2){
                v[i-lgS1 + 1] = 1;
                cnt++;
            }
        }
        out << cnt << endl;
        cnt = 0;
        for(int i = 0; i < lgS2 && cnt < 1000; i++)
            if(v[i] == 1){
                cnt++;
                out << i << " ";
            }
    }

    in.close(); out.close();
    return 0;
}