Cod sursa(job #2922199)

Utilizator alex_braslasuBraslasu Alexandru alex_braslasu Data 5 septembrie 2022 21:14:30
Problema Potrivirea sirurilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <cstring>

#define N_MAX 2000010

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char s[N_MAX], pattern[N_MAX];
int n, m, i, cnt, pz, top, p[N_MAX], sol[N_MAX];

int main()
{
    ios::sync_with_stdio(false);
    f.tie(0), g.tie(0);
    f >> (pattern + 1) >> (s + 1);
    n = strlen(pattern + 1);
    m = strlen(s + 1);
    for (i = 2; i <= n; ++i)
    {
        if (pattern[cnt + 1] == pattern[i])
        {
            while (i <= n && pattern[cnt + 1] == pattern[i])
            {
                p[i] = ++cnt;
                ++i;
            }
            --i;
        }
        cnt = 0;
    }
    pz = 1;
    for (i = 1; i <= m; ++i)
        if (s[i] == pattern[pz])
        {
            while (pz <= n && i <= m && s[i] == pattern[pz])
                ++pz, ++i;
            if (pz > n)
            {
                sol[++top] = i - n - 1;
                if (top == 1000)
                    break;
            }
            --pz; --i;
            (p[pz]) ? pz = p[pz] : pz = 1;
            --i;
        }
    g << top << '\n';
    for (i = 1; i <= min(top, 1000); ++i)
        g << sol[i] << " ";
    return 0;
}