Pagini recente » Cod sursa (job #2059571) | Cod sursa (job #1190890) | Cod sursa (job #693976) | Cod sursa (job #692486) | Cod sursa (job #1711995)
#include <fstream>
#include <cstring>
#define MAX_LENGTH 2000005
using namespace std;
char text[MAX_LENGTH], pattern[MAX_LENGTH];
size_t patternLg, textLg, nrMatches;
size_t matches[1005];
int pi[MAX_LENGTH];
inline int min(int x, int y){
return (x < y) ? x : y;
}
void MakePi(){
int k = -1;
pi[0] = -1;
for (int i = 1; i < patternLg; ++i){
while (k >= 0 && pattern[i] != pattern[k + 1]){
k = pi[k];
}
if (pattern[i] == pattern[k + 1]) ++k;
pi[i] = k;
}
}
void SearchText(){
int k = -1;
for (int i = 0; i < textLg; ++i){
while (k >= 0 && pattern[k + 1] != text[i]){
k = pi[k];
}
if (pattern[k + 1] == text[i]) ++k;
if (k == patternLg - 1){
if (nrMatches < 1000){
matches[nrMatches] = i - k;
}
++nrMatches;
k = pi[k];
}
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(pattern, MAX_LENGTH);
fin.getline(text, MAX_LENGTH);
patternLg = strlen(pattern);
textLg = strlen(text);
MakePi();
SearchText();
fout << nrMatches << '\n';
for (int i = 0; i < min(nrMatches, 1000); ++i){
fout << matches[i] << ' ';
}
return 0;
}