Cod sursa(job #1311304)

Utilizator andreimdvMoldovan Andrei andreimdv Data 7 ianuarie 2015 22:35:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
//KMP by andreimdv https://www.youtube.com/watch?v=kBW6oPaVjq0
#include <fstream>
#include<cstring>
#include<vector>
using namespace std;

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

char s[2000010],t[2000010];
int n,i,m,nr,p[2000010];
int k,q,snr;
vector<int> v;
vector<int> ::iterator it;

int main()
{

    fin>>(t+1)>>(s+1);

    //compute-prefix-function
    m=strlen(t+1);
    k=0;
    for(i=2;i<=m;++i) //parcurgem sirul t pentru a gasi prefixele din acesta: ex ABCdefABdcABC
    {
        while(k>0 && t[k+1]!=t[i]) //prefixul nu mai continua
            k=p[k];

        if(t[k+1]==t[i]) //prefixul se prelungeste
            k=k+1;

        p[i]=k; //vectorul p retine lungimea prefixului pentru fiecare pozitie
    }
    //************************

    q=0; // numarul de caractere care sunt la fel
    n=strlen(s+1);
    for(i=1;i<=n;++i)
    {
        while(q>0&& t[q+1]!=s[i])
            q=p[q];
        if(t[q+1]==s[i])//urmatorul caracter este la fel
            q=q+1;
        if(q==m)
        {
            nr++;
            v.push_back(i-m);
            if(nr==1000)
            break;

        q=p[q];// folosind vectorul constrit cu ajutorul functiei de precomputare a prefixelor, in loc sa parcurgem integral textul sarim la urmatorul loc in care se poate afla sirul cautat
        }
    }
    fout<<nr<<'\n';
    for(it=v.begin();it!=v.end();it++)
    fout<<*it<<" ";
    return 0;
}