Cod sursa(job #2088040)

Utilizator FrequeAlex Iordachescu Freque Data 14 decembrie 2017 18:23:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 2000005;

char pattern[NMAX], text[NMAX];
int phi[NMAX]; /// phi[i] = cel mai lung sufix din pattern care se termina in i si e si prefix pattern
int phi1[NMAX]; /// phi1[i] = cel mai lung sufix din text care se termina in i si e prefix in pattern
vector<int>ans;

void Init()
{
    int lena = strlen(pattern + 1), lenb = strlen(text + 1);
   for (int i = 2; i <= lena; i++)
   {
        int last = phi[i - 1];
        while (last > 0 && pattern[i] != pattern[last + 1]) last = phi[last];
        if (pattern[i] == pattern[last + 1]) phi[i] = last + 1;
        else phi[i] = last;
   }

   for (int i = 1; i <= lenb; i++)
   {
        int last = phi1[i - 1];
        while (last > 0 && text[i] != pattern[last + 1]) last = phi[last];
        if (text[i] == pattern[last + 1]) phi1[i] = last + 1;
        else phi1[i] = last;

        if (phi1[i] == lena)
            ans.push_back(i - lena);
   }
}

int main()
{
    fin >> (pattern + 1) >> (text + 1);
    Init();

    fout << ans.size() << "\n";
    for (int i = 0; i < 1000 && i < ans.size(); i++)
        fout << ans[i] << " ";
    return 0;
}