Cod sursa(job #1149526)

Utilizator dumytruKana Banana dumytru Data 21 martie 2014 22:55:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <iostream>
#include <string.h>
#include <vector>

#define nmax 2000002
using namespace std;

char t[nmax],p[nmax];
long long pi[nmax];
vector<int> sol;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

long long n,m;

void COMPUTE_PREFIX_FUNCTION()
{
    pi[1]=0;
    long long k=0,i;
    for(i=2;i<=m;i++)
    {
        while(k>0 && p[k+1] != p[i])
            k=pi[k];
        if(p[k+1]==p[i])
            k++;
        pi[i] = k;
    }
}

void kmp_match()
{
    long long q,i;
    COMPUTE_PREFIX_FUNCTION();
    q=0;
    for(i=1;i<=n;i++)
    {
        while(q>0 && p[q+1] != t[i])
            q=pi[q];
        if(p[q+1]==t[i])
            q++;
        if(q==m)
        {
            sol.push_back(i-m);
            q=pi[q];
        }
    }
}
unsigned minim(long long a, long long b)
{
    if(a>b)return b;
    else return a;
}
int main()
{
    f.getline(p,nmax);
    f.getline(t,nmax);
    long long i;n=strlen(t);m=strlen(p);
    for (i = m; i; i--) p[i] = p[i-1]; p[0] = ' ';
    for (i = n; i; i--) t[i] = t[i-1]; t[0] = ' ';
    kmp_match();
    g<<sol.size()<<'\n';
    for(i=0;i<minim(1000,sol.size());i++)
        g<<sol[i]<<' ';
    f.close();g.close();
    return 0;
}