Cod sursa(job #1877647)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 13 februarie 2017 17:06:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <cstdlib>
#define LMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a,b;
vector<int> rez;
int F[LMAX];
vector<int> kmp(string a,string b)
{
    int N=a.size();
    int M=b.size();
    memset(F,0,sizeof(F));
    ///failure function
    for(int i=2;i<=M;i++)
    {
        int j=F[i-1];
        while(1)
        {
            if(b[j]==b[i-1])
               {F[i]=j+1;break;}
            if(j==0) break;
            j=F[j];
        }
    }
    int i,j;i=j=0;
    vector<int> ap;
    while(1)
    {
        if(j==N) break;
        if(b[i]==a[j])
        {
            i++;j++;
            if(i==M)
            {
                ap.push_back(j-M);
                if(ap.size()>=1000) return ap;
                i=F[i];
            }
        }
        else if(i==0) j++;
        else i=F[i];
    }
    return ap;
}
int main()
{
    f>>a>>b;
    rez=kmp(b,a);
    g<<rez.size()<<"\n";
    for(auto it:rez)
        g<<it<<" ";
    f.close();
    g.close();
    return 0;
}