Cod sursa(job #1621535)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 29 februarie 2016 19:48:22
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

#define ll long long unsigned
#define pb push_back
#define mp make_pair

char A[2000005];
char B[2000005];
int pref[2000005];
vector <int> v;

void prep(){
    int i;
    int l = strlen(A+1);
    int q = 0;
    for(i = 2;i <= l;i++){
        while(q && A[q+1] != A[i]){
            q = pref[q];
        }
        if(A[q+1] == A[i]){
            q++;
        }
        pref[i] = q;
    }
}

int kmp(){
    int i;
    int ans = 0;
    int l = strlen(B+1);
    int lm = strlen(A+1);
    int q = 0;
    for(i = 2;i <= l;i++){
        while(q && A[q+1] != B[i]){
            q = pref[q];
        }
        if(A[q+1] == B[i]){
            q++;
        }
        if(q == lm){
            ans++;
            if(ans <= 1000){
                v.pb(i-lm);
            }
        }
    }
    return ans;
}

int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s",A+1);
    scanf("%s",B+1);
    prep();
    printf("%d\n",kmp());
    for(auto it : v){
        printf("%d ",it);
    }
    return 0;
}