Cod sursa(job #3253049)

Utilizator satzaFoldesi Richard satza Data 1 noiembrie 2024 07:32:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");
char A[4000004], B[2000002];
int N, M, pi[4000002], sol, ans[1002];

int main(){
    in >> A;
    N = strlen(A);
    in >> B;
    M = strlen(B);
    if(N == 1){
        for(int i = 0; i < M; i++){
            if(A[0] == B[i]){
                sol = sol + 1; ans[sol] = i;
            }
        }
    }
    else{
        A[N] = '#';
        for(int i = 0; i < M; i++) A[N + i + 1] = B[i];
        M = M + N + 1;
        pi[0] = 0;
        for(int i = 1; i < M; i++){
            int j = pi[i - 1];
            while(j > 0 and A[i] != A[j])
                j = pi[j - 1];
            if(A[i] == A[j]) j = j + 1;
            if(j == N){
                sol = sol + 1; ans[sol] = i - N - N;
            }
            pi[i] = j;
        }
    }
    if(sol > 1000) sol = 1000;
    out << sol << "\n";
    for(int i = 1; i <= min(sol, 1000); i++) out << ans[i] << " ";
    return 0;
}