Cod sursa(job #2667647)

Utilizator alexia208160Popescu Alexia Maria alexia208160 Data 3 noiembrie 2020 18:35:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <cstring>
#include <string>

using namespace std;

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

int pattern[2000001];

void Pattern( string s1, int n)
{
    for(int i = 0; i < n; i++)
        if(pattern[i + 1] == 0)
            for(int j = i + 1; j < n; j++)
                if(s1[i] == s1[j])
                    pattern[j + 1] = i + 1;
}

int main()
{
    string s1, s2;
    fin >> s1 >> s2;
    int l1 = s1.length(), l2 = s2.length(), sol[1000];
    Pattern(s1, l1);
    int i = 0, j = 0, k = 0, ct = 0;
    while(i < l2)
    {
        int ii = i, jj = j;
        if(s2[i] == s1[j])
        {
            while(s2[ii] == s1[jj])
            {
                ii++;
                jj++;
                if(jj == l1)
                {
                    k++;
                    if(ct < 1000)
                        sol[ct++] = ii - l1;
                }
            }
            i += (pattern[j] + 1);
            j = pattern[j];
        }
        else
        {
            j = pattern[j];
            i++;
        }
    }
    fout << k << '\n';
    for(i = 0; i < ct; i++)
        fout << sol[i] <<' ';
}