Cod sursa(job #3158415)

Utilizator ililogIlinca ililog Data 18 octombrie 2023 18:21:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[2000001], b[2000001];
int la, lb;
int lps[2000001];
int ans;
int pos[1001];

int main() {

    fin >> a >> b;
    la = strlen(a), lb = strlen(b);
    
    for (int i = la; i>=1; i--) {
        a[i] = a[i-1];
    }
    a[0] = ' ';
    
    for (int i = lb; i>=1; i--) {
        b[i] = b[i-1];
    }
    b[0] = ' ';
    
    lps[1] = 0;
    int j = 0;
    for (int i = 2; i<=la; i++) {
        while (j && a[j+1] != a[i]) {
            j = lps[j];
        }
        if (a[j+1] == a[i]) {
            j++;
        }
        lps[i] = j;
    }
    
    j = 0;
    for (int i = 1; i<=lb; i++) {
        while (j && a[j+1] != b[i]) {
            j = lps[j];
        }
        if (a[j+1] == b[i]) {
            j++;
        }
        
        if (j == la) {
            j = lps[la];
            ans++;
            if (ans <= 1000) {
                pos[ans] = i-la;
            }
        }
    }
    
    fout << ans << '\n';
    for (int i = 1; i<=min(ans, 1000); i++) {
        fout << pos[i] << " ";
    }
    
    return 0;
}