Cod sursa(job #3253033)

Utilizator satzaFoldesi Richard satza Data 31 octombrie 2024 23:01:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;

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

int main(){
    in >> A;
    N = strlen(A);
    in >> B;
    M = strlen(B);
    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 and sol < 1000; 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;
    }
    out << sol << "\n";
    for(int i = 1; i <= sol; i++) out << ans[i] << " ";
    return 0;
}