Cod sursa(job #1879620)

Utilizator sfechisalin@yahoo.comSfechis Alin [email protected] Data 15 februarie 2017 01:26:22
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

vector<int>prefix(string pattern)
{
    int k = 0;
    vector<int>pi(pattern.size(),0);
    for (int i = 2; i <= pattern.size(); ++i)
    {
        while (k > 0 && pattern[k+1] != pattern[i])
            k = pi[k];
        if (pattern[k+1] == pattern[i])
            k++;
        pi[i] = k;
    }
    return pi;
}

vector<int>KMP(string subsir,string sir)
{
    int k = 0 , m = subsir.size();
    vector<int>answ;
    vector<int>pi = prefix(subsir);
    for(int i = 1; i <= sir.size(); ++i)
    {
        while (k > 0 && subsir[k+1] != sir[i])
            k = pi[k];
        if (subsir[k+1] == sir[i])
            k++;
        if (k == m - 1)
        {
            answ.push_back(i-m+1);
           k = pi[k];
        }
    }
    return answ;
}

int main()
{
    string A,B,S;
	getline(fin,S);
	B = " ";
	B += S;
	getline(fin,S);
	A = " ";
	A += S;
    vector<int>answ = KMP(B,A);
    int d = answ.size();
    int length = min(d,1000);
    fout << length << "\n";
    for (int i = 0; i < length; ++i)
        fout << answ[i] << " ";
    return 0;
}