Cod sursa(job #1139822)

Utilizator RobertSSamoilescu Robert RobertS Data 11 martie 2014 15:17:43
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
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];
void overlap(){
	int i = 0, j = 1;
	
	while(j<n){
		
		if(a[i] == a[j]){
			ov[j] = 1;
			i++; j++;
			while(a[i] == a[j]){
				ov[j] = 1 + ov[j-1];
				i++; j++;
			}
			i=0; j--;
		}
		j++;
	}
	
	
}


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

		if(ov[j-1]){
			k = i-ov[j-1];
			j = ov[j-1];
		}else{
			if(k == i) i++;
			k = i;
			j = 0;
		}
		
	}
	


}

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