Cod sursa(job #3150954)

Utilizator Redstoneboss2Fabian Lucian Redstoneboss2 Data 19 septembrie 2023 10:23:09
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

#define cin fin
#define cout fout

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

void printVector(vector<int>& vec);

int main(){

	string a, b;
	vector<int> pos, aux;

	cin >> a >> b;

	aux.resize(a.size());
	aux[0] = -1;

	for(int i = 1, j = -1; i < aux.size(); i++){
		aux[i] = -1;

		if(a[i] == a[j + 1]){
			j++;
			aux[i] = j;
		}else{
			while(j != -1 && a[i] != a[j + 1]){
				j = aux[j];
			}

			if(a[i] == a[j + 1]){
				j++;
				aux[i] = j;
			}
		}
	}

	// printVector(aux);

	for(int i = 0, j = -1; i < b.size(); i++){
		if(b[i] == a[j + 1]){
			j++;

            if(j == a.size() - 1){
				pos.push_back(i - j);
				j = aux[j];
				continue;
			}
		}

        while(j != -1 && b[i] != a[j + 1]){
            j = aux[j];
        }
	}

	cout << pos.size() << '\n';

	for(int i = 0; i < 1000 && i < pos.size(); i++)
    {
        cout << pos[i] << ' ';
    }

	return 0;
}

void printVector(vector<int>& vec)
{
    for(auto& e : vec)
    {
        cout << e << ' ';
    }

    cout << '\n';
}