Cod sursa(job #1785605)

Utilizator ZeratulVeress Szilard Zeratul Data 21 octombrie 2016 17:40:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <string>
#include <queue>

#define FOR(i,k,v) for(i = k;i<=v;i++)

using namespace std;

string a,b,c;
queue <int> Q;
int i,j,q;
int mereta,meretb,meretc;
int s[2000001*2];

void check(int i)
{
    if(i > mereta and s[i] == mereta)
    {
        Q.push(i - mereta - 1);
    }
}

int calculate_border(int i, int j)
{
    int x = 1;
    while(c[i] == c[j] and i < meretc)
    {
        x++;
        i++;
        j++;
    }
    return x;
}

int main()
{
    ifstream be("strmatch.in");
    ofstream ki("strmatch.out");

    getline(be,a);
    getline(be,b);
    mereta = a.size();
    meretb = b.size();

    c = a + "#" + b;
    //cout<<c<<endl;

    i = 1;
    meretc = c.size();
    s[0] = 0;

    while(i < meretc)
    {
        if(c[i] == c[0])
        {
            s[i] = calculate_border(i+1,1);
            check(i);
            q = s[i] + i;
            i++;
            j = 1;
            while(s[j] + i < q and i<q)
            {
                s[i] = s[j];
                check(i);
                i++;
                j++;
            }
        }
        else
        {
            s[i] == 0;
            check(i);
            i++;
        }
    }

    /*FOR(i,0,meretc-1)
    {
        cout<<s[i]<<" ";
    }*/

    ki<<Q.size()<<endl;
    int counter = 0;
    while(!Q.empty() and counter < 1000)
    {
        counter++;
        ki<<Q.front()<<" ";
        Q.pop();
    }

    return 0;
}