Cod sursa(job #1221904)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 21 august 2014 17:40:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <list>
#include <cstring>
#define DIM 2000011
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[DIM],B[DIM],*p;
int P[DIM],n,m,L,nr;

list<int> sol;

int main(void){
    register int i,j;

    f>>A+1>>B+1;
    n=strlen(A+1);
    L=0,P[1]=0;

    for(p=A+2;*p;p++){
        while(*p!=A[L+1] && L!=0) L=P[L];
        if(*p==A[L+1]) L++;
        P[p-A]=L;
    }

    L=0;
    for(p=B+1;*p;p++){
        while(*p!=A[L+1] && L) L=P[L];
        if(*p==A[L+1]) L++;
        if(L==n){
            nr++;
            if(nr<=1000)
                sol.push_back(p-B-L);
        }
    }

    g<<nr<<"\n";
    for(list<int>::iterator it=sol.begin();it!=sol.end();it++)
        g<<*it<<" ";
    f.close();
    g.close();
    return 0;
}