Cod sursa(job #2567247)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 3 martie 2020 16:10:23
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int NMAX = 2000005;
char s[NMAX];
int z[NMAX];
vector <int> sol;

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s", s + 1);
    int n = (int)strlen(s + 1);
    scanf("%s", s + n + 1);
    int m = (int)strlen(s + 1);
    int st = 1, dr = 1;
    z[1] = 1;
    for(int k = 2; k <= m; k++) {
        if(s[k] != s[1]) {
            z[k] = 0;
        }
        else {
            int poz = k;
            if(k <= dr) {
                poz = k + z[dr - k + 1] - 1;
            }
            while(poz <= m && s[poz] == s[poz - k + 1]) {
                poz++;
            }
            poz--;
            if(dr < poz) {
                dr = poz;
                st = k;
            }
            z[k] = poz - k + 1;
        }
    }///ABACABBCABABAB
    for(int k = n + 1; k <= m; k++) {
        if(z[k] >= n) {
            sol.push_back(k - n);
        }
    }
    printf("%d\n", sol.size());
    for(int i = 0; i < sol.size() && i < 1000; i++) {
        printf("%d ", sol[i] - 1);
    }
    return 0;
}