Cod sursa(job #2246372)

Utilizator agrtAndreea G agrt Data 27 septembrie 2018 00:16:22
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

int main(int argc , char *argv[]) {
	ifstream x;
	ofstream y;
	x.open("strmatch.in");
	y.open("strmatch.out");
	
	
	string a, b;
	x >> b;
	x >> a;
	
	int skip = 0
	if (b.size() > a.size())
	    skip = 1;

	vector<int> v, results;
	v.resize(b.size());
	
	if (!skip) {
		unsigned int i = 1, j = 0 ;
		v[0] = -1;
		int fnd = 0;
		
		while (j >= 0 && i < b.size()) {
			if (b[i] == b[j]) {
				v[i] = j + 1;
				i++;
				j++;
				fnd = 1;
			} else {
				if ((i < b.size() - 1) && !fnd) {
					i++;
					v[i] = 0;
				} else {
					j = v[j - 1];
					if (j == 4294967295) {
						fnd = 0;
						j = 0;
					}
				}
			}
		}

		j = 0;
		i = 0;
		int mtch = 0;
		

		while (i < a.size()) {
			if (b[j] == a[i]) {
			   if (j == b.size() - 1) {
				   j = v[j - 1];
				   results.push_back(i - j);
			   } else {
				   i++;
				   j++;
			   }
			   mtch = 1;
		   } else {
			   if (mtch) {
				   if (j > 0) {
					   j = v[j - 1];
					   if (j == 4294967295) {
							j = 0;
							mtch = 0;
					   }
				   } else {
					   j = 0;
					   mtch = 0;
				   } 
			   } else { 
				   i++;
			   }
		   }
		}
	}
	y << results.size() << "\n";
	for (unsigned int i = 0; i< results.size(); i++)
		y << results[i] << " ";
	
	x.close();
	y.close();
    return 0;
}