Cod sursa(job #1984827)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 26 mai 2017 09:31:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 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;
    }
    int last = 0;
    if(s[0] == pattern[0])
        last = 1;
    for(int i = 1; i < s.size(); ++i)
    {
        pos = last;
        while(pos != 0 && s[i] != pattern[pos])
            pos = pi[pos - 1];
        if(s[i] == pattern[pos])
            pos++;
        last = 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;
}