Cod sursa(job #1061930)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 20 decembrie 2013 14:43:58
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include<fstream>
#include<iostream>
#include<string.h>
using namespace std;
char a[2000005],b[2000005];
int n,m,q,pi[2000005],pos[1010],sol;

void citire() {

    ifstream in("strmatch.in");
    int i;

    in.getline(a,2000001);
    in.getline(b,2000001);

    for(i=0;a[i]<='z'&&a[i]>='0';i++);
    m=i;
    for(i=0;b[i]<='z'&&b[i]>='0';i++);
    n=i;
    for(i=m;i>=1;i--)
        a[i]=a[i-1];
    for(i=n;i>=1;i--)
        b[i]=b[i-1];
    a[0]=b[0]=' ';

    in.close();

}

void prefix() {

    int i;

    for(i=2,pi[1]=0;i<=m;i++) {

        while(q&&a[q+1]!=a[i])
            q=pi[q];

        if (a[q+1]==a[i])
            ++q;
        pi[i] = q;

    }

}

void solve() {

    int i;

    for (i=1;i<=n;i++) {

        while (q && a[q+1] != b[i])
            q = pi[q];
        if (a[q+1] == b[i])
            ++q;
        if (q == m)
        {
            q = pi[m];
            ++sol;
            if (sol <= 1000)
                pos[sol] = i-m;
        }
    }

}

void afisare() {

    ofstream out("strmatch.out");
    int i;

    out<<sol<<'\n';
    if(sol>1000)
        sol=1000;

    for(i=1;i<=sol;i++)
        out<<pos[i]<<" ";
    out<<'\n';

    out.close();

}

int main() {

    citire();
    prefix();
    solve();
    afisare();

    return 0;

}