Pagini recente » Istoria paginii runda/oni_cl8 | Profil Al3ks1002 | Istoria paginii runda/pixelcup | Istoria paginii problema/muzica | Cod sursa (job #1811580)
/**
* Worg
*/
#include <string>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAX_LEN = (1 + 2000000) << 1;
const int MAX_SOL = 1000;
/*-------- Input data --------*/
string A, B;
/*-------- Z-Algorithm --------*/
string S;
int Z[MAX_LEN];
/*-------- Solution --------*/
int solutionCount;
vector< int > Solution;
/*-------- --------*/
void readInput() {
fin >> A >> B;
}
void runZ_Algorithm() {
int N = S.size();
int L = -1, R = -1;
for(int i = 1; i < N; i++) {
if(i > R) {
/* nu ne putem baza pe vreun Z-Box anterior */
if(S[0] == S[i]) {
L = i;
R = i - 1;
for(int j = 0, k = i; k < N && S[j] == S[k]; j++, k++) {
Z[i] ++;
R ++;
}
} else {
Z[i] = 0;
}
} else {
/* ne bazam pe Z-Boxul in care suntem */
int before = i - L;
if(Z[before] < R - i + 1) {
Z[i] = Z[before];
} else {
Z[i] = R - i + 1;
L = i;
for(int before = Z[i]; R + 1 < N && S[R + 1] == S[before]; before++, R++) {
Z[i] ++;
}
}
}
}
}
void getSolution() {
int N = S.size();
int M = A.size();
for(int i = M; i < N; i++) {
if(Z[i] >= M) {
solutionCount ++;
if(solutionCount <= MAX_SOL) {
Solution.push_back(i - M);
}
}
}
}
void writeOutput() {
fout << solutionCount << '\n';
for(int i : Solution) {
fout << i << " ";
}
}
int main() {
readInput();
S = A + B;
runZ_Algorithm();
getSolution();
writeOutput();
return 0;
}