Cod sursa(job #288328)

Utilizator raula_sanChis Raoul raula_san Data 25 martie 2009 18:34:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

#define MAX_L 2000002

using namespace std;

int C, N, M, Pi[MAX_L];
string A, B;

vector <int> Sol;

void Prefix()
{
     int k = 0, i;
     
     Pi[1] = 0;
     for ( i = 2; i <= N; ++i )
     {
         while(k > 0 && A[k] != A[i-1])
                 k = Pi[k];
                 
         if(A[k] == A[i-1])
                 ++ k;
                 
         Pi[i] = k;
     }
}

int main()
{
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);
    
    cin >> A >> B;
    N = A.length();
    M = B.length();
    
    Prefix();

    int q = 0, i;
    
    for ( i = 1; i <= M; ++i )
    {
        while(q > 0 && A[q] != B[i-1])
                q = Pi[q];
                
        if(B[i-1] == A[q])
                ++ q;
                
        if(q == N && Sol.size() <= 1000)
        {
             Sol.push_back(i-N);
             q = Pi[q];
             ++ C;
        }
        else if(q == N)
             ++ C;
    }

    printf("%d\n", C);
    
    for ( i = 0; i < Sol.size(); ++i )
        printf("%d ", Sol[i]);
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}