Pagini recente » Cod sursa (job #1684840) | Cod sursa (job #2012202) | Istoria paginii utilizator/mihaigurgu | Cod sursa (job #1594590) | Cod sursa (job #1690156)
#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, 2000000);
fin.getline(s2 + 1, 2000000);
len1 = strlen(s1 + 1);
len2 = strlen(s2 + 1);
kmp(len1, len2);
fout << npotriviri << "\n";
for(int i = 1; i <= npotriviri; ++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 < 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;
}
}