Cod sursa(job #2258639)

Utilizator AnimusFabian Animus Data 11 octombrie 2018 19:01:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

#define MAX 10000

int main()
{
    long long int v1 = 0, v2 = 0;
    long long int h1 = 0, h2 = 0;
    string a, b;
    in >> a;
    in >> b;
    int n = a.length();
    int m = b.length();
    int p1 = 1, p2 = 1;

    for(int i = n-1; i >= 0; --i){
        v1 += a[i] * p1;
        p1 *= 27;
    }

    for(int i = n-1; i >= 0; --i){
        v2 += a[i] * p2;
        p2 *= 29;
    }

    v1 = v1 % 10007;
    v2 = v2 % 666013;

    int c = 0;
    int r = 0;

    int is[MAX];

    for(int i = 0; i < m; ++i){
        if(i <= m-n){
            string substring = "";
            h1 = 0;
            h2 = 0;
            p1 = 1;
            p2 = 1;
            for(int j = i; j < n+i; ++j){
                substring += b[j];
            }
            for(int j = substring.length()-1; j >= 0; --j){
                h1 += substring[j] * p1;
                p1 *= 27;
                h2 += substring[j] * p2;
                p2 *= 29;
            }
            h1 = h1 % 10007;
            h2 = h2 % 666013;

            if(h1 == v1 && h2 == v2){
                c++;
                is[r] = i;
                r++;
            }
        }
    }

    out << c << '\n';

    for(int i = 0; i < r; ++i){
        out << is[i] << " ";
    }
}