Cod sursa(job #2762619)

Utilizator Tudor_StefanaStefana Tudor Tudor_Stefana Data 8 iulie 2021 20:32:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <string>
using namespace std;

const int MaxN = 2000010;

int pi[MaxN];
int sol[1010];

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int main()
{
    string A;
    string B;
    getline(cin, A);
    getline(cin, B);

    A = ' ' + A;
    B = ' ' + B;

    int q = 0;
    pi[1] = 0;
    for(int i = 2; i < (int)A.size(); ++i){
        while(q && A[q+1] != A[i]){
            q = pi[q];
        }
        if(A[q+1] == A[i]) ++q;

        pi[i] = q;
    }
    int cnt = 0;
    q = 0;

    for(int i = 1; i < (int)B.size(); ++i){
        while(q && A[q+1] != B[i]){
            q = pi[q];
        }
        if(A[q+1] == B[i]) ++ q;
        if(q == (int)A.size() - 1) {
            q = pi[q];
            ++ cnt;
            if(cnt <= 1000){
                sol[cnt] = i-(int)A.size() + 1;
            }
        }
    }

    cout << cnt << '\n';
    for(int i = 1; i <= min(1000, cnt); ++i){
        cout << sol[i] << ' ';
    }
    return 0;
}