Cod sursa(job #2263805)

Utilizator rebecca0312Andrei Rebecca rebecca0312 Data 19 octombrie 2018 12:10:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include<cstdio>
#include<iostream>
#include<queue>
#include<string>
using namespace std;

const int NMAX=2000005;
int T[NMAX];

queue<int> indx;
string pat,txt;


void precomp(){
    int i=1,j=0;
    while(i<(int)pat.length()){
        if(pat[i]==pat[j]){
            T[i]=j+1;
            i++,j++;
        }
        else
            if(j!=0){
                while(j!=0 && pat[i]!=pat[j])
                    j=T[j-1];
            }
            else
                i++;
    }
}

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int i=0,j=0,sol=0;
    cin>>pat>>txt;
    txt.push_back('.');
    precomp();
    while(i<=(int)txt.length()){
        if(j>=(int)pat.length()){
            if(indx.size()<1000)
                indx.push(i-pat.length());
            sol++;
            j=T[j-1];
        }
        if(txt[i]==pat[j])
            i++,j++;
        else
            if(j!=0)
                j=T[j-1];
            else
                i++;
    }
    printf("%d\n", sol);
    while(!indx.empty()){
        printf("%d ", indx.front());
        indx.pop();
    }
    return 0;
}