Cod sursa(job #1651665)

Utilizator bogdan2510Ionut Bogdan bogdan2510 Data 13 martie 2016 18:09:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000005],B[2000005];
vector <int> Sol;
int nA,nB,pi[2000005];
void make_prefix(){
    int q=0;
    for(int i=2;i<=nA;i++){
        while(q && A[q+1]!=A[i]){
            q=pi[q];
        }
        if(A[q+1]==A[i]){
            ++q;
        }
        pi[i]=q;
    }
}
int main()
{
    f>>A+1>>B+1;
    nA=strlen(A+1);
    nB=strlen(B+1);
    make_prefix();
    int q=0;
    for(int i=1;i<=nB;i++){
        while(q && A[q+1]!=B[i]){
            q=pi[q];
        }
        if(A[q+1]==B[i]){
            ++q;
        }
        if(q==nA){
            if(Sol.size()<1000){
                Sol.push_back(i-nA);
            }
        }
    }
    g<<Sol.size()<<"\n";
    for(int i=0;i<Sol.size();i++){
        g<<Sol[i]<<" ";
    }
    return 0;
}