Cod sursa(job #2753396)

Utilizator Paul0516Berindeie Paul Paul0516 Data 22 mai 2021 19:38:41
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 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++)
    {
        j = suf[i - 1];
        while (j > 0 && t[j] != t[i])
            j = suf[j - 1];
        if (j > 0 || t[i] == t[j])
            suf[i] = j + 1;
    }
}

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

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