Pagini recente » Cod sursa (job #274825) | Cod sursa (job #708766) | Cod sursa (job #1755813) | Cod sursa (job #1513307) | Cod sursa (job #2764018)
/*
Z-algorithm
*/
#include <iostream>
#include <fstream>
#include <cstring>
#define LMAX 2000000 //doua milioane
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s[2 * LMAX + 1 + 1];
int Z[2 * LMAX + 1 + 1];
int main()
{
fin.getline(s, LMAX + 1);
int LGA = strlen(s);
s[ LGA ] = '$';
fin.getline(s + LGA + 1, LMAX + 1);
int lg = strlen(s);
Z[0] = lg;
int left = 0;
int right = 0;
for(int i = 1; i < lg; i++){
if(i > right){
left = i;
right = i;
while(right < lg && s[right] == s[right - left]){
right++;
}
right--;
Z[i] = right - left + 1;
}
else {
//sunt inauntrul box-ului
int pI = i - left; //pozitia corespunzatoare din stanga
if( i - 1 + Z[pI] < right ){
Z[i] = Z[pI];
}
else {
//verific daca mai apar in plus din dreapta
left = i;
while(right < lg && s[right] == s[right - left]){
right++;
}
right--;
Z[i] = right - left + 1;
}
}
}
int nrAparitii = 0;
for(int i = LGA + 1; i < lg; i++){
if(Z[i] == LGA){
nrAparitii++;
}
}
fout << nrAparitii << "\n";
int afis = 0;
for(int i = LGA + 1; i < lg; i++){
if(Z[i] == LGA && afis < 1000){
fout << i - (LGA + 1) << ' ';
afis++;
}
}
return 0;
}