Cod sursa(job #2753406)

Utilizator Paul0516Berindeie Paul Paul0516 Data 22 mai 2021 20:09:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <climits>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>

using namespace std;

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

char s[2000002], t[2000002];
int suf[2000002], indici[2000002];

void sufixe(int n)
{
    int i, j = 0;
    for (i = 1; i < n; i++)
    {
        while (j > 0 && t[j] != t[i])
            j = suf[j - 1];
        if (t[i] == t[j])
            j++;
        suf[i] = j;
    }
}

int main()
{
    int i, j, n, m, z = 0;
    f.getline(t, 2000002);
    f.getline(s, 2000002);
    n = strlen(s);
    m = strlen(t);
    sufixe(m);
    j = 0;
    for (i = 0; i < n; i++)
    {
        while (j != 0 && s[i] != t[j])
        {
            j = suf[j - 1];
        }
        if (s[i] == t[j])
        {
            j++;
        }
        if (j == m)
        {
            if (z<=1000)
                indici[++z] = i - m + 1;
            j = suf[j-1];

        }
    }
    g << z << "\n";
    for (i = 1; i <= min(z,1000); i++)
    {
        g << indici[i] << " ";
    }
    return 0;
}