Cod sursa(job #1280862)

Utilizator timicsIoana Tamas timics Data 2 decembrie 2014 17:13:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<string>
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
string s,t;
int N,M,pi[2001000],q;
vector<int> rez;

int main() {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    cin>>s>>t;
    N = s.size();
    M = t.size();

    s.insert(0," ");
    t.insert(0," ");
    
    q = 0;
    for(int i=2;i<=N;++i) {
        while(q && s[q+1] != s[i]) {
            q = pi[q];
        }
        if(s[q+1] == s[i]) {
            ++q;
        }
        pi[i] = q;
    }
    
    q = 0;
    for(int i=1;i<=M;++i) {
        while(q && s[q+1]!=t[i]) {
            q = pi[q];
        }
        if(s[q+1] == t[i]) {
            ++q;
        }
        if(q==N) {
            rez.push_back(i-N);
            q = pi[N];
        }

    }
    
    int k = rez.size();
    k = min(1000,k);
    printf("%d\n",k);
    for(int i=0;i<k;++i) {
        printf("%d ",rez[i]);
    }
    return 0;
}