Cod sursa(job #2580866)

Utilizator valen.valentinValentin Valeanu valen.valentin Data 14 martie 2020 11:58:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#include <unordered_map>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>

#define nmax 2000010
#define fst first
#define snd second
#define pb push_back
#define MOD 998244353
#define SZ(x) ((int)(x.size()))

using namespace std;

typedef pair<int, int> pii;
typedef long long int ll;

int n, m, len;
int z[2 * nmax];
char a[nmax], b[nmax], c[2 * nmax];

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s", a + 1);
    scanf("%s", b + 1);

    int n = strlen(a + 1);
    int m = strlen(b + 1);

    len = n;

    for (int i = 1; i <= n; i++) c[i] = a[i];

    c[++len] = '@';

    for (int i = 1; i <= m; i++) c[++len] = b[i];

    z[1] = 0;
    int l = 0, r = 0;

    for (int i = 2; i <= len; i++) {

        if (i > r) {

            l = r = i;

            while (r <= len && c[r] == c[r - l + 1]) r++;

            z[i] = r - l; r--;
        }
        else
        {
            int pos = i - l + 1;

            if (i + z[pos] <= r) z[i] = z[pos]; else
            {
                l = i;

                while (r <= len && c[r] == c[r - l + 1]) r++;

                z[i] = r - l; r--;
            }
        }
    }
    
    vector <int> vc;

    for (int i = n + 1; i <= len; i++)
        if (z[i] == n) vc.pb(i - n - 2);

    printf("%d\n", SZ(vc));

    for (int i = 0; i < SZ(vc); i++) printf("%d ", vc[i]);

    // IMPORTANT!!!!!
    // Are you missing something????
    // check limits, int or ll

    return 0;
}