Cod sursa(job #2239623)

Utilizator pinteastefanPintea Teodor Stefan pinteastefan Data 11 septembrie 2018 13:53:53
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

char A[2000005], B[2000005];
int pi[2000005], n, m, pos[1024];

void compute_prefix()
{
    int i, k = 0;
    pi[1] = 0;
    for (i = 2; i <= n; i++)
    {
        while((k > 0) && (A[k + 1] != A[k])){
            k = pi[k];
        }
        if (A[k + 1] == A[i]){
            k += 1;
        }
        pi[i] = k;
    }
}

int main() {
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    int i, q = 0, nr = 0;
    f.get(A, sizeof(A));
    f.get();
    f.get(B, sizeof(B));
    for (int i = 0; i < sizeof(A); i++){
        if (A[i] >= 'a' && A[i] <= 'z' || A[i] >= 'A' && A[i] <= 'Z' || A[i] >= '0' && A[i] <= '9')
            n++;
        else break;
    }
    for (int i = 0; i < sizeof(B); i++){
        if (B[i] >= 'a' && B[i] <= 'z' || B[i] >= 'A' && B[i] <= 'Z' || B[i] >= '0' && B[i] <= '9')
            m++;
        else break;
    }
    for (i = n; i ; i -- ){
        A[i] =  A[i - 1];
    }
    A[0] = ' ';
    for (i = m; i ; i -- ){
        B[i] = B[i - 1];
    }
    B[0] = ' ';
    compute_prefix();

    for (i = 1; i<= m; i++)
    {
        while ( q && A[q + 1] != B[i]){
            q = pi[q];
        }
        if (A[q + 1] == B[i]){
            ++q;
        }
        if (q == n){
            q = pi[n];
            ++ nr;
            if ( nr <= 1000) {
                pos[nr] = i - n;
            }
        }
    }
    g << nr << "\n";
    for (i = 1; i <= nr; i++)
    {
        g << pos[i]<< " ";
    }
    return 0;
}