Cod sursa(job #1750922)

Utilizator bogdanluncasubogdan bogdanluncasu Data 31 august 2016 14:29:32
Problema Potrivirea sirurilor Scor 6
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include<string.h>
using namespace std;
#define SIZE 2000000
int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	char * w1=(char*)malloc(SIZE);
	char * w2=(char*)malloc(SIZE);
	
	cin>>w1>>w2;
	int * v=(int*)malloc(sizeof(int)*strlen(w1));
	int * c=(int*)malloc(sizeof(int)*strlen(w2));
	v[0]=0;
	int vindex=1,len=0;
	while (vindex < strlen(w1))
    {
       if(w1[vindex]==w1[len]){
       		len++;
       		v[vindex]=len;
       		vindex++;
       }else{
       	if(len!=0){
       		len=0;
       	}else{
	       	v[vindex]=0;
	       	vindex++;
       	}
       }
    }
    
    int w1len=strlen(w1);
    int w2len=strlen(w2);
    //cout<<w1len<<endl<<w2len<<endl;
    //for(int i=0;i<w1len;i++)cout<<v[i]<<" ";
    
    int i,count=0;
    	for(int j=0;j<w2len;j++){
    		for(i=0;i<w1len;i++){
    			//cout<<w1[i]<<" "<<w2[j]<<endl;
    			if(w2[j]!=w1[i]){
    				j+=v[i]-1;
    				i=w1len;
    			}else j++;
    		}
    		if(i==w1len-1){
    			c[count++]=j;
    		}
    	}
    cout<<count<<endl;
    for(i=0;i<count;i++){
    	cout<<c[i]<<" ";
    }
	
}