Cod sursa(job #3149992)

Utilizator Redstoneboss2Fabian Lucian Redstoneboss2 Data 14 septembrie 2023 12:27:50
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

#define cin fin
#define cout fout

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

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;
			}
		}
	}

	for(int i = 0, j = -1, enterAux; i < b.size() && pos.size() < 1000; i++){
        enterAux = 1;

		if(b[i] == a[j + 1]){
			j++;
            enterAux = 0;

            if(pos.size() < 1000 && j == a.size() - 1){
				pos.push_back(i - j);
				j = aux[j];
				enterAux = 1;
			}
		}

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

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

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

	for(auto& e : pos)
    {
        cout << e << ' ';
    }

	return 0;
}