Cod sursa(job #1008856)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 11 octombrie 2013 23:32:21
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;
const int Nmax = 2000005;

vector<int> sol;
char A[ Nmax ],B[ Nmax ];
int N,M,K , prefix[ Nmax ];

void read()
{
    scanf("%s\n%s",&A,&B);
    N = strlen(A)-1;
    M = strlen(B)-1;
}


inline void pre() {
    prefix[1] = 0;
    K = 0;
    for(int i = 2 ; i <= N ; ++ i) {
        while( K > 0 && A[K+1] != A[i])
            K = prefix[K];
        if(A[K+1] == A[i])
            ++ K;
        prefix[i] = K;
    }
}

inline void KMP() {
    K = 0;
    for(int i = 1 ; i <= M ; ++ i) {
        while( K > 0 && A[K+1] != B[i])
            K = prefix[K];
        if(A[K+1] == B[i])
            ++ K;
        if(K == N)
            sol.push_back(i-K);
    }

}

inline void print()
{
    printf("%d\n",sol.size());
    int x = sol.size();
    for(int i = 0 ; i < min(1000,x);++i)
        printf("%d ",sol[i]);
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    read();
    pre();
    KMP();
    print();

    return 0;
}