Cod sursa(job #1579680)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 24 ianuarie 2016 22:46:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
// Problema Strmatch - InfoArena ( www.infoarena.ro/problema/strmatch )
// Solutie partiala cu C++ Strings si unoredered_map
#include <string>
#include <unordered_map>
#include <fstream>
#include <vector>
 
#define in "strmatch.in"
#define out "strmatch.out"
#define len 2000007
#define pb push_back
 
using namespace std;
ifstream cin(in);
ofstream cout(out);
 
int sze1, sze2, nrSol;
string str1, str2, tmp;
unordered_map <string, bool> RabinKarp;
vector <int> vecSol;
 
int main()
{
    cin >> str1 >> str2;
    sze1 = str1.size();
    sze2 = str2.size();
    RabinKarp[str1] = true;
    for(int i = 0 ; i< sze2 - sze1 + 1; ++i)
    {
        tmp.replace(0, len, str2, i, sze1);
        if(RabinKarp[tmp] == true)
        {
            nrSol ++;
            vecSol.pb(i);
        }
        else
        {
            RabinKarp.erase(tmp);
        }
    }
    cout << nrSol << "\n";
    for(int i = 0; i< nrSol; ++i)
    {
        cout << vecSol[i] << " ";
    }
    cout << "\n";
}