Cod sursa(job #2673262)

Utilizator BalasaRaduBalasa Radu BalasaRadu Data 16 noiembrie 2020 13:20:01
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;

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

char s1[2000005], s2[2000005];

int prefix[2000005], sol[1005];


int main()
{
    fin.getline(s1,NULL);
    fin.getline(s2,NULL);

    int poz = 0;

    int j = 0;


    ///Prima parte-prefixarea
    for(int i = 1; i < strlen(s1); i++)
    {
        while(s1[i] != s1[j] && j != 0)
            j = prefix[j - 1];///prefix[-1] nu exista

        if(s1[i] == s1[j])
            j++;

        prefix[i] = j;///prefix = aux
    }

    j = 0;

    int k = 0;

    ///Calcularea solutiilor-partea a doua
    for(int i = 0 ; i < strlen(s2); i++)
    {
        while(s2[i] != s1[j] && j != 0)
            j = prefix[j - 1];

        if(s2[i] == s1[j])
        {
            j++;
            if(j == strlen(s1))
                {
                    k++;

                    if(k <= 1000)
                        sol[k] = i - j + 1;
                    j = prefix[j - 1];
                }
        }
    }
    fout << k << '\n';

    for(int i = 1; i <= min(1000, k); i++)
        fout << sol[i] << " ";

    return 0;
}