Cod sursa(job #1630028)

Utilizator Player1Player 1 Player1 Data 4 martie 2016 21:05:38
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <stdio.h>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int main(){
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	string s1,s2;
	fin>>s1>>s2;
	//fout<<s1<<endl<<s2<<endl;
	if(s1.size() > s2.size()){
		fout<<"0";
		return 0;
	}
	int len1 = s1.size(), len2 = s2.size();
	int nrResults = 0;
	vector<vector<int> > result;
	vector<int> indexes;
	if(s1[0] == s2[0]){
		vector<int> aux(1,1);
		result.push_back(aux);
	} else {
		vector<int> aux(1,0);
		result.push_back(aux);
	}

	for(int i=1;i < len2; i++){
		vector<int> aux(1,0);
		result.push_back(aux);
		//fout<<endl<<"result["<<i-1<<"]: ";
		for(int j = 0; j < result[i-1].size(); j++){
			//fout<<result[i-1][j]<<"  ";
			if((result[i-1][j] != 0) && (result[i-1][j] < len1)){
				int p = result[i-1][j];
				if(s1[p] == s2[i])
					result[i].push_back(p+1);
					if(p == len1){
						nrResults ++;
						if(indexes.size() < 1000)
							indexes.push_back(i-p);
					}
			}
		}
		if(s2[i] == s1[0])
			result[i].push_back(1);
	}
	
	fout<<nrResults<<endl;
	if(indexes.size() == 0)
		return 0;
	else
		fout<<indexes[0];
	for(int i = 1; i < indexes.size(); i++)
		fout<<" "<<indexes[i];
	
	return 0;
}