Cod sursa(job #2096777)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 29 decembrie 2017 19:20:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int base = 103;
const int nmax = 2000000;

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

string s1;
string s2;
ull h[nmax]; //hash-urile prefixelor (se folosesc la rolling hash)
ull target; //hash-ul string-ului ce trebuie gasit
ull shift;
vector <int> sol;
int nsol;

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

    target = 0;
    shift = 1;
    for(int i=0; i < s1.size(); i++) {
        target = target * base + (s1[i] - 'A');
        shift = shift * base;
    }

    h[0] = s2[0] - 'A';
    for(int i = 1; i < s2.size(); i ++)
        h[i] = h[i-1] * base + (s2[i] - 'A');
    for(int i = 0; i + s1.size() <= s2.size(); i ++)
    {
        ull pretender = h[i+s1.size()-1];
        if(0 < i)
            pretender -= (h[i-1]*shift);
        if(pretender == target){
            nsol ++;
            if(nsol <= 1000)
                sol.push_back(i);
        }
    }
    out << nsol << "\n";
    for(int i = 0;i < sol.size();i ++)
        out << sol[i] << " ";
    return 0;
}