Cod sursa(job #1646449)

Utilizator gapdanPopescu George gapdan Data 10 martie 2016 16:16:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 100005

using namespace std;

char s[NMAX],p[NMAX];
int n,m,i,j,ant[NMAX],nr,k;
vector<int>sol;

void prefix()
{
    int i;
    k=0;ant[1]=0;
    for(i=2;i<=n;++i)
    {
        while(p[k+1] != p[i] && k>0) k=ant[k];
        if(p[k+1] == p[i]) ++k;
        ant[i]=k;
    }
}

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f.getline(p+1,NMAX);
    f.getline(s+1,NMAX);
    n=strlen(p+1);
    m=strlen(s+1);
    prefix();
    k=0;
    for(i=1;i<=m;++i)
    {
        while(s[i] != p[k+1] && k > 0) k=ant[k];
        if(p[k+1] == s[i]) ++k;
        if(k == n)
        {
            ++nr;
            if(nr < 1000) sol.push_back(i-n);
        }
    }

    g<<nr<<"\n";
    for(i=0;i<sol.size();++i) g<<sol[i]<<" ";
    return 0;
}