Cod sursa(job #1667751)

Utilizator vlad6001Pintilie Vlad vlad6001 Data 29 martie 2016 10:40:10
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int i, j, q, pref[2000005], q2, gasite, poz[2000005];
char v[2000005], t[2000005];

int main()
{
    fin.getline(v, 2000005);
    q = strlen(v);
    fin.getline(t, 2000005);
    q2 = strlen(t);
    j = 0;
    pref[0] = 0;

    for(i=1; i <= q; i++)
    {
        if(v[i] == v[j])
        {
            pref[i] = pref[i-1]+1;
            j++;
        }
        else
        {
            while(v[j] != v[i] && j != 0)
            {
                j = pref[j-1];
            }
        }
    }

    j = 0;
    for(i=0; i < q2; i++)
    {
        if(t[i] == v[j])
        {
            j++;
        }
        else
        {
            if(j != 0)
            j = pref[j-1];
        }

        if(j == q)
        {
            gasite++;
            poz[gasite] = i-q+1;
            j=pref[j-1];
        }
    }

    fout << gasite << '\n';
    for(i=1; i <= gasite; i++)
    fout << poz[i] << ' ';
}