Pagini recente » Cod sursa (job #1264892) | Cod sursa (job #806075) | Cod sursa (job #1880205) | Cod sursa (job #2225208) | Cod sursa (job #1690163)
#include <fstream>
#include <cstring>
using namespace std;
char s1[2000005];
char s2[2000005];
int prefix[2000001];
int potriviri[1001];
int npotriviri;
int citesteLinie(char s[], FILE *f);
void kmp(int len1, int len2);
void formarePrefix(int len);
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int len1, len2;
fin.getline(s1 + 1, 2000005);
fin.getline(s2 + 1, 2000005);
len1 = strlen(s1 + 1);
len2 = strlen(s2 + 1);
kmp(len1, len2);
fout << npotriviri << "\n";
for(int i = 1; i <= npotriviri && i <= 1000; ++i)
fout << potriviri[i] << " ";
return 0;
}
void kmp(int len1, int len2){
int k = 0;
formarePrefix(len1);
for(int i = 1; i <= len2; ++i){
while(k > 0 && s2[i] != s1[k + 1])
k = prefix[k];
if(s2[i] == s1[k + 1])
++k;
if(k == len1){
++npotriviri;
if(npotriviri <= 1000)
potriviri[npotriviri] = i - len1;
}
}
}
void formarePrefix(int len){
int k = 0;
prefix[1] = 0;
for(int i = 2; i <= len; ++i){
while(k > 0 && s1[i] != s1[k + 1])
k = prefix[k];
if(s1[i] == s1[k + 1])
++k;
prefix[i] = k;
}
}