Cod sursa(job #1221893)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 21 august 2014 17:31:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 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;

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!=0;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 && sol.size()<1000;p++){
        while(*p!=A[L+1] && L) L=P[L];
        if(*p==A[L+1])
            L++;
        if(L==n)
            sol.push_back(p-B-L);
    }

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