Cod sursa(job #1508928)

Utilizator DoraBenzoVelicu Teodora DoraBenzo Data 23 octombrie 2015 10:22:38
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 2000001

using namespace std;
ifstream f("strmatch.in");
ofstream o("strmatch.out");

char a[nmax], b[nmax];
int poz[10001], pref[nmax], lp, ls, nr, k;

void citire()
{
    f.getline(a, nmax);
    f.getline(b, nmax);
    lp = strlen(a);
    ls = strlen(b);
}

void pattern()
{
    int i, j;
    i=1;
    j=0;
    pref[0] = 0;
    while(i < lp)
        if(a[i] == a[j])
        {
            pref[i] = j+1;
            i++;
            j++;
        }
        else
            if(j == 0)
                pref[i++]=0;
            else
                j=pref[j-1];
}

int cautare()
{
    int i, j;
    i = 0;
    j = 0;
    while(i < ls)
        if(b[i] == a[j])
        {
            i++;
            j++;
            if(j == lp)
            {
                poz[k++] = i - lp;
                j = pref[j-1];
                nr++;
            }
        }
        else
            if(j == 0)
                i++;
            else
                j = pref[j-1];
    return nr;
}

int main()
{
    citire();
    pattern();
    o<<cautare()<<"\n";

    if(k > 1000)
        k = 1000;
    for(int i=0; i<k; i++)
        o<<poz[i]<<" ";
    return 0;
}