Cod sursa(job #1922385)

Utilizator Train1Train1 Train1 Data 10 martie 2017 17:15:21
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 3.47 kb

#include <fstream>
#include <cstring>
#include <queue>
#define maxSize 2000001
#define prim 73
#define mod 104729
#define mod2 104743
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s1[maxSize], s2[maxSize];
queue <int> q;
int main()
{
    fin.getline(s1, maxSize);
    fin.getline(s2, maxSize);
    int l1 = strlen(s1) - 1;
    int l2 = strlen(s2) - 1;
    long long hash11 = 0, hash12 = 0, hash21= 0, hash22 = 0, power = 1;
    if (l2 < l1) {
        fout<<"0";
        return 0 ;
    }
    hash11 = s1[0];
    hash12 = s1[0];
    hash21 = s2[0];
    hash22 = s2[0];
    for(int i = 1; i <= l1; i++) {
        power = (power * prim) % mod;
        hash11 = (hash11 + s1[i] * power)% mod;
        hash21 = (hash21 + s2[i] * power)% mod;
        hash12 = (hash12 + s1[i] * power)% mod2;
        hash22 = (hash22 + s2[i] * power)% mod2;
    }
    if(l2 == l1 && hash11 == hash21 && hash12 == hash22) {
        fout<<"1\n0";
        return 0;
    }
    int nr = 0;
    for (int i = l1 + 1; i <= l2; i++) {
        if(hash11 == hash21 && hash12 == hash22) {
            nr++;
            q.push(i - l1 -1);
        }
        hash21 = (((hash21 - s2[i - l1 - 1]) / prim) + (s2[i] * power) % mod) % mod;
        hash22 = (((hash22 - s2[i - l1 - 1]) / prim) + (s2[i] * power) % mod2) % mod2;
    }
    if(hash11 == hash21 && hash12 == hash22) {
        nr++;
        q.push(l2 - l1);
    }
    fout<<nr<<'\n';
    int k = 0;
    while(!q.empty()) {
        fout<<q.front()<<' ';
        k++;
        if(k == 1000)
            break;
        q.pop();
    }
    fin.close();
    fout.close();
    return 0;
}
/*
#include <fstream>
#include <cstring>
#include <queue>
#define maxSize 2000001
#define prim 73
#define mod 104729
#define mod2 104743
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s1[maxSize], s2[maxSize];
queue <int> q;
int main()
{
    fin.getline(s1, maxSize);
    fin.getline(s2, maxSize);
    int l1 = strlen(s1) - 1;
    int l2 = strlen(s2) - 1;
    long long hash11 = 0, hash12 = 0, hash21= 0, hash22 = 0, power = 1;
    int value = 'A' - 1;
    if (l2 < l1) {
        fout<<"0";
        return 0 ;
    }
    hash11 = s1[0] - value;
    hash12 = s1[0] - value;
    hash21 = s2[0] - value;
    hash22 = s2[0] - value;
    for(int i = 1; i <= l1; i++) {
        power = (power * prim) % mod;
        hash11 = (hash11 + (s1[i] - value) * power)% mod;
        hash21 = (hash21 + (s2[i] - value) * power)% mod;
        hash12 = (hash12 + (s1[i] - value) * power)% mod2;
        hash22 = (hash22 + (s2[i] - value) * power)% mod2;
    }
    if(l2 == l1 && hash11 == hash21 && hash12 == hash22) {
        fout<<"1\n0";
        return 0;
    }
    int nr = 0;
    for (int i = l1 + 1; i <= l2; i++) {
        if(hash11 == hash21 && hash12 == hash22) {
            nr++;
            q.push(i - l1 -1);
        }
        hash21 = (((hash21 - (s2[i - l1 - 1] - value)) / prim) + ((s2[i] - value) * power) % mod) % mod;
        hash22 = (((hash22 - (s2[i - l1 - 1] - value)) / prim) + ((s2[i] - value) * power) % mod2) % mod2;
    }
    if(hash11 == hash21 && hash12 == hash22) {
        nr++;
        q.push(l2 - l1);
    }
    fout<<nr<<'\n';
    int k = 0;
    while(!q.empty()) {
        fout<<q.front()<<' ';
        k++;
        if(k == 1000)
            break;
        q.pop();
    }
    fin.close();
    fout.close();
    return 0;
}
*/