Cod sursa(job #1769745)

Utilizator sulzandreiandrei sulzandrei Data 3 octombrie 2016 01:27:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");
void kmp_table(string& w,vector<int>& t)
{
    t.resize(w.size()+1);
    int pos = 2,cnd = 0;
    t[0] = -1,t[1] = 0;
    while(pos <= w.size())
    {
        if(w[pos-1] == w[cnd])
        {
            t[pos] = cnd+1;
            cnd++;
            pos++;
        }
        else if(cnd>0)
            cnd = t[cnd];
        else
        {
            t[pos] = 0;
            pos++;
        }
    }
}
void kmp(string &s, string&w, vector<int> &pos)
{
    int m = 0 , i = 0;
    vector<int> t;
    //cout<<w<<"\n"<<s;
    kmp_table(w,t);
    while( m + i <s.size() )
    {
        if(w[i] == s[m+i])
        {
            if(i == w.size()-1)
                pos.push_back(m);
            i++;
        }
        else
            if(t[i] > -1)
                m = m + i - t[i],i = t[i];
            else
                m++ , i = 0;
    }
}
int main()
{
    vector<int> pos;
    string s,w;
    in >> w >> s;
    kmp(s,w,pos);

    out<<pos.size()<<'\n';
    for(int j = 0 ; j < std::min((int)pos.size(),1000); j++)
        out<<pos[j]<<" ";

    return 0;
}