Cod sursa(job #2753429)

Utilizator Paul0516Berindeie Paul Paul0516 Data 22 mai 2021 20:41:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 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[1001];


void asezare(int n, char s[])
{
    int i;
    for (i = n; i > 0; i--)
        s[i] = s[i - 1];

    s[0] = 0;
}

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

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

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