Cod sursa(job #3238976)

Utilizator Allie28Radu Alesia Allie28 Data 1 august 2024 02:14:22
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_map>
#include <cstdio>

using namespace std;

//ifstream fin("repetat.in");
//ofstream fout("repetat.out");

const int LMAX = 2000005;

char a[LMAX], b[LMAX];
int pi[LMAX], sol[1005], n, m;

//pi[i] --> lungimea celui mai lung prefix sufix

void Pi(){
    int i, k;
    k = 0;
    for (i = 2; i <= n; i++) {
        while (k && a[k + 1] != a[i]) {
            k = pi[k];
        }
        if (a[k + 1] == a[i]) {
            k++;
        }
        pi[i] = k;
    }
}

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s%s", (a + 1), (b + 1));
    n = strlen(a + 1);
    m = strlen(b + 1);
    if (n > m) {
        printf("%d\n", 0);
        return 0;
    }
    Pi();
    int k = 0, i;
    sol[0] = 0;
    for (i = 2; i <= m; i++) {
        while (k && a[k + 1] != b[i]) {
            k = pi[k];
        }
        if (a[k + 1] == b[i]) k++;
        if (k == n) {
            sol[0]++;
            if (sol[0] <= 1000) sol[sol[0]] = i;
        }
    }
    printf("%d\n", sol[0]);
	for(int i = 1; i <= sol[0] && i <= 1000; i++){
		printf("%d ", sol[i] - n);
	}


//    fin.close();
//    fout.close();
    return 0;
}