Cod sursa(job #1520322)

Utilizator dragos000Cojanu Dragos dragos000 Data 8 noiembrie 2015 16:44:01
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

char a[100],b[100];
int n,m,pi[100],rez[100],N;
void citire()
{
    ifstream f("strmatch.in");
    f.getline(a,100);f.getline(b,100);
    f.close();
    n=strlen(a);
    m=strlen(b);
}

void prefix()
{
    int q=0,i;

    for (i=2;i<=m;i++)
    {
        while (q>0&&b[q]!= b[i])
            q=pi[q-1];
        if (b[q]==b[i])
            q++;
        pi[i] = q;
    }
}

void fct()
{

    int q=0;

    for(int i=1;i<=n;i++)
        {
        while(q>0 && b[q]!=a[i])
        q=pi[q-1];

        if(b[q]==a[i]) q++;
        if(q==m)
        {
        q=pi[q];
        N++;
        rez[N]=i-m;
        }
        }

}



int main()
{
    citire();
    prefix();
    fct();

    ofstream g("strmatch.out");
    g<<N<<endl;
    for(int i=1;i<=N;i++)
        g<<rez[i]<<" ";

    return 0;
}