Cod sursa(job #1139748)

Utilizator RobertSSamoilescu Robert RobertS Data 11 martie 2014 14:04:55
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

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

char a[100], b[100];
int n, m;

vector<int> v;

void read(){
	fin.get(a,100);
	n = strlen(a);
	fin.get();
	fin.get(b,100);
	m = strlen(b);
}

int ov[100];
bool ovFunction(int &i, int &j){
	bool ok = false;
	while(a[i] == a[j]){
		ov[j] = ov[i]+1;
		i++; j++;
		ok = true;
	}

	return ok;
}

void overlap(){
	int i = 0, j = 0;
	ov[i] = 0; ov[j+1] = 1;
	while(j<n){
		j++;
		bool ok = true;
		while(ok){
			ok = ovFunction(i,j);
			if(ok) i = 0;
		}
	}
	
}


void solve(){
	int k=0; 
	int i = 0, j = 0;
	
	
	while(i<m){
		
		while(a[j] == b[i] && j<n){
			i++; j++;
		}
		
		if(j == n) v.push_back(k);
		
		
		if(ov[j-1] > 0) k = i-ov[j-1];
		else{
			if(k == i) i++;
			k = i;
		}
		
		if(j > 0) j = ov[j-1];
		
	}

}

int main(){
	read();
	overlap();
	solve();
	
	fout << v.size() << '\n';
	for(size_t i=0; i<v.size(); i++){
		fout << v[i] << " ";
	}
	fout << '\n';
	return 0;
}