Cod sursa(job #1984826)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 26 mai 2017 09:30:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

vector<int> KMP(const string &s, const string &pattern)
{
    vector<int> ret;
    if(s.size() < pattern.size())
        return ret;
    vector<int> pi;
    pi.resize(pattern.size());
    pi[0] = 0;
    int pos = 0;
    for(int i = 1; i < pattern.size(); ++i)
    {
        pos = pi[i-1];
        while(pos != 0 && pattern[i] != pattern[pos])
            pos = pi[pos - 1];
        if(pattern[i] == pattern[pos])
            pos++;
        pi[i] = pos;
    }
    vector<int> d;
    d.resize(s.size());
    if(s[0] == pattern[0])
        d[0] = 1;
    for(int i = 1; i < s.size(); ++i)
    {
        pos = d[i-1];
        while(pos != 0 && s[i] != pattern[pos])
            pos = pi[pos - 1];
        if(s[i] == pattern[pos])
            pos++;
        d[i] = pos;
        if(pos == pattern.size())
            ret.push_back(i - pos + 1);
    }
    return ret;
}

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    string a, b;
    in >> a >> b;
    vector<int> sol = KMP(b, a);
    out << sol.size() << "\n";
    for(int i = 0; i < sol.size() && i < 1000; ++i)
        out << sol[i] << " ";
    in.close();
    out.close();
    return 0;
}