Cod sursa(job #1398792)

Utilizator kiunyAndrei Gavrila kiuny Data 24 martie 2015 13:26:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector <int> T;
vector <int> gasite;
void kmpSearch(string s, string w)
{
    int m = 0, i = 0;
    int ls = s.length();
    int lw = w.length();

    while(m+i < ls)
    {
        if(w[i] == s[m+i])
        {
            if(i == lw-1)
            {
                gasite.push_back(m);
            }
            i++;
        }
        else
        {
            if(T[i] > -1)
            {
                m += i - T[i];
                i = T[i];
            }
            else
            {
                i = 0;
                m++;
            }
        }
    }
}

void fillTable(string w)
{
    int pos = 2;
    int cnd = 0;
    int lw = w.length();
    T.push_back(-1);
    T.push_back(0);

    while(pos <= lw)
    {
        if(w[pos-1] == w[cnd])
        {
            cnd++;
            T.push_back(cnd);
            pos++;
        }
        else if(cnd > 0)
        {
            cnd = T[cnd];
        }
        else
        {
            T.push_back(0);
            pos++;
        }
    }
}

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int main()
{
    string s1, s2;
    f >> s1 >> s2;
    fillTable(s1);
    kmpSearch(s2, s1);
    g << gasite.size() << "\n";
    for(int i = 0; i < gasite.size() && i < 1000; i++)
    {
        //cout << i;
        g << gasite[i] << " ";
    }
    return 0;
}