Cod sursa(job #1806135)

Utilizator marcdariaDaria Marc marcdaria Data 14 noiembrie 2016 20:54:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

vector <int> getMatch(string s,string t)
{
    int n=s.size();
    int m=t.size();

    //calcularea vectorului pi
    vector <int> pi(n); //pi[i] = x litera cu indicele de pozitie i indica lungimea celui mai lung sufix care este si prefix
    int k=-1;
    pi[0]=-1; //initializam primul sufix care este si prefix ca avand lungime 0
    for(int i=1;i<n;++i) //parcuregem toate caracterele sirului s
    {
        while(k!=-1 && s[k+1]!=s[i])
             k=pi[k];

        if(s[k+1]==s[i])
        ++k;
        pi[i]=k;
    }

    //cautarea sirului t in sirul s
    k=-1;
    vector <int> v;
    for(int i=0;i<m;++i)
    {
        while(k!=-1 && s[k+1]!=t[i])
        k=pi[k];
        if(s[k+1]==t[i])
        ++k;
        if(k==n-1)
        v.push_back(i-k);
    }
    return v;
}

int main()
{
    string s,t;
    getline(fin,s);
    getline(fin,t);

    vector <int> matches=getMatch(s,t);
    fout<<matches.size()<<'\n';
    for(int i=0;i<min(1000,int(matches.size()));++i)
       fout<<matches[i]<<" ";

    fin.close();
    fout.close();
    return 0;
}