Cod sursa(job #146046)

Utilizator moga_florianFlorian MOGA moga_florian Data 1 martie 2008 09:04:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream>
using namespace std;
#define Nmax 2000005

char A[Nmax], B[Nmax];
int pi[Nmax];
int poz[1024];

int main(){

    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    
    fin>>A>>B;
    
    int sol = 0;
    
    pi[0] = -1;
    int k = -1,L;
    for(int i=1;A[i];i++){
        while(k>=0 && A[k+1] != A[i])
            k = pi[k];
            
        if(A[k+1] == A[i])
            k++;
            
        pi[i] = k;
        L = i;
    }
    L++;
    
    k=-1;
    for(int i=0;B[i];i++){
        while(k>=0 && A[k+1] != B[i])
            k = pi[k];
            
        if(A[k+1] == B[i])
            k++;
        
        if(k == L-1){
            sol++;
            if(sol <= 1000)
                poz[sol] = i-L+1;
            k = pi[k];
        }
    }

    fout<<sol<<"\n";
    for(int i=1;i<=((sol>1000)?1000:sol); i++)
        fout<<poz[i]<<" ";
        
    fin.close();
    fout.close();
    return 0;
}