Cod sursa(job #583181)

Utilizator stef93Stefan Gilca stef93 Data 18 aprilie 2011 17:16:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

int urm[2000003];
int pr[2000003];
int n,m,nr;
string t;
string p;

void urmatorul(string &c)
{
    int k=-1,x;
    urm[0]=0;
    for(x=1;x<m;x++)
    {
        while(k>0&&c[k+1]!=c[x])k=urm[k];
        if(c[k+1]==c[x])k++;
        urm[x]=k;
    }
}

int main()
{
    int i,x=-1;
    ifstream in("strmatch.in");
    in>>p;
    in>>t;
    n=t.size();m=p.size();
    urmatorul(p);
    for(i=0;i<t.size();i++)
    {
        while(x>0&&p[x+1]!=t[i])x=urm[x];
        if(p[x+1]==t[i])x++;
        if(x==m-1)
        {
            pr[nr++]=i-m+1;
            x=urm[x];
        }
    }
    ofstream out("strmatch.out");
    out<<nr<<'\n';
    if(nr<1000)
    for(i=0;i<nr;i++)
    out<<pr[i]<<' ';
    else
    for(i=0;i<1000;i++)
    out<<pr[i]<<' ';
    return 0;
}