Cod sursa(job #709976)

Utilizator cmiNCosmin Poieana cmiN Data 8 martie 2012 19:06:30
Problema Potrivirea sirurilor Scor 34
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <locale>
#include <string>
#include <algorithm>
using namespace std;


const int DIM = 1000;
typedef collate<char> cc_t;
string str, pat;
vector<int> matchPos;


inline long long hash(const string& arg, const cc_t& coll)
{
    return coll.hash(arg.data(), arg.data() + arg.size());
}


void solve()
{
    const cc_t& coll = use_facet<cc_t>(locale());
    long long patHash = hash(pat, coll);
    int ind = min(pat.size(), str.size());
    string tmp = str.substr(0, ind);
    for (; ind <= str.size() && matchPos.size() < DIM; ++ind) {
        //cerr << tmp << endl;
        if (hash(tmp, coll) == patHash) matchPos.push_back(ind - pat.size());
        tmp.erase(0, 1);
        tmp.push_back(str[ind]);
    }
}


int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> pat >> str;
    solve();
    fout << matchPos.size() << '\n';
    for (int i = 0; i < matchPos.size(); ++i) fout << matchPos[i] << ' ';
    fout << endl;
    fin.close();
    fout.close();
    return 0;
}