Cod sursa(job #2721085)

Utilizator DragosC1Dragos DragosC1 Data 11 martie 2021 15:54:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;

char a[2000001];
char b[2000001];
int table[2000001];
int lA, lB;
vector<int> ind;

void read() {
	ifstream f("strmatch.in");
	f.getline(a, 2000001);
	f.getline(b, 2000001);
	f.close();
}

void solve() {
	int i = 0, j = 1;
	lA = strlen(a);
	lB = strlen(b);
	while (j < lA) {
		if (a[i] == a[j]) {
			table[j] = i + 1;
			i++, j++;
		}
		else if (i != 0)
			i = table[i - 1];
		else j++;
	}
	j = 0;
	for (i = 0; i < lB;) {
		if (b[i] == a[j]) 
			i++, j++;
		else if (j != 0)
			j = table[j - 1];
		else i++;
		if (j == lA) {
			ind.emplace_back(i - j);
			j = table[j - 1];
		}
	}
}

void output() {
	ofstream g("strmatch.out");
	int nr, i;
	g << ind.size() << '\n';
	if (ind.size() > 1000)
		nr = 1000;
	else nr = ind.size();
	for (i = 0; i < nr; i++)
		g << ind[i] << ' ' ;
	g.close();
}

int main() {
	read();
	solve();
	output();
	return 0;
}