Cod sursa(job #1051053)

Utilizator RobertSSamoilescu Robert RobertS Data 9 decembrie 2013 17:47:02
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");


#define MAX_N 1000
int n, m;
char s1[MAX_N], s2[MAX_N];

void read(){
	char f1[MAX_N], f2[MAX_N];
	fin.get(f1,MAX_N);
	fin.get();
	fin.get(f2,MAX_N);
	
	int n1 = strlen(f1);
	int n2 = strlen(f2);
	
	s1[0] = s2[0] = 'x';
	
	
	strcat(s1,f2);
	strcat(s2,f1);
	
	n = strlen(s1)-1;
	m = strlen(s2)-1;
	

}


int ol[MAX_N];

vector<int>list;


void overLap(){
	for(int k=1; k<=m; k++){
		char c = s2[k+1];
		int v = ol[k];
		while(s2[v+1] !=c && v!=0){
			v = ol[v];
		}
		if(s2[v+1] == c)
			ol[k+1] = v+1;
		else
			ol[k+1] = 0;
	}
}



void solve(){
	int i=1, j=1, k=1;
	while(n-k >= m){
		while(j <=m && s1[i] == s2[j]){
			i++,  j++;
		}
		
		if(j > m) list.push_back(k-1);
		if(ol[j-1] > 0){
			k = i - ol[j-1];
		}else{
			if(i==k) i++;
			k = i;
		}
		if(j > 1) j= ol[j-1]+1;
	}

	if(k!=i){
		bool ok = true;
		for(int l=1; l<=m; l++){
			if(s2[l]!=s1[k-1+l]) ok = false;
		}
		if(ok) list.push_back(k-1);
	}
	
}

int main(){
	read();
	overLap();
	solve();
	
	
	fout << list.size() << endl;
	for(size_t i = 0; i<list.size(); i++){
		fout << list[i] << " ";
	}
return 0;
}