Cod sursa(job #1360768)

Utilizator zpaePopescu Andreea zpae Data 25 februarie 2015 17:44:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <string>
using namespace std;
#define N 2000003

int n,m,u[N],p[N];
string a, b;

void prefix()
{
    int i,q=0;
    for(i=2;i<=n;i++)
    {
        while(q&&a[q+1]!=a[i])
            q=u[q];
        if(a[q+1]==a[i])
            q++;
        u[i]=q;
    }
}

int main()
{
    ifstream in ("strmatch.in");
    ofstream out ("strmatch.out");
    int i,q=0,k=0;
    getline(in,b);
    getline(in,a);
    a='.'+a;
    b=','+b;
    n=a.length()-1;
    m=b.length()-1;
    prefix();
    for(i=1;i<=m;i++)
    {
        while(q&&a[q+1]!=b[i])
            q=u[q];
        if(a[q+1]==b[i])
            q++;
        if(q==n)
        {
            out<<i-n+1<<' ';
            q=u[n];
            k++;
        }
    }
    out<<endl<<k<<endl;
    return 0;
}