Cod sursa(job #2589344)

Utilizator anghelus_vladAnghelus Ionut Vlad anghelus_vlad Data 26 martie 2020 10:57:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>
#define NMAX 4000002

using namespace std;

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

char s1[NMAX], s2[NMAX];
int pref[NMAX], n;

void f_pref(char s[NMAX], int pref[NMAX], int n) {
    pref[0] = 0;
    for (int i = 1; i < n; i++) {
        int j = i;
        while (j > 0 && s[pref[j - 1]] != s[i]) {
            j = pref[j - 1];
        }
        if (j == 0)
            pref[i] = 0;
        else
            pref[i] = pref[j - 1] + 1;
    }
}

int main()
{
    int ct=0, lg1, i;

    fin.getline(s1, NMAX);
    lg1=strlen(s1);
    fin.getline(s2, NMAX);
    strcat(s1, "$");
    strcat(s1, s2);
    n=strlen(s1);
    f_pref(s1, pref, n);
    for(i=0; i<n; ++i)
        if(pref[i]==lg1)
            ct++;
    fout << ct << '\n';
    ct=0;
    for(i=0; i<n; ++i)
        if(pref[i]==lg1)
        {
            if(ct<1000)
            {
                fout << i-2*lg1 << ' ';
                ct++;
            }
            else
                break;
        }
    return 0;
}