Cod sursa(job #2246369)

Utilizator agrtAndreea G agrt Data 27 septembrie 2018 00:03:51
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 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;
	
	if (b.size() > a.size())
	    return 1;
	int num = 0;
	vector<int> v, results;
	v.resize(b.size());
	
	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 == -1) {
				    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 == -1) {
    	                j = 0;
    	                mtch = 0;
    	           }
	           } else {
	               j = 0;
    	           mtch = 0;
	           } 
	       } else { 
	           i++;
	       }
	   }
	}
	
	y << results.size() << "\n";
	for (int i =0; i< results.size(); i++)
		y << results[i] << " ";
	
	x.close();
	y.close();
    return 0;
}