Pagini recente » Cod sursa (job #1244195) | Cod sursa (job #262875) | Cod sursa (job #2908917) | Cod sursa (job #1462308) | Cod sursa (job #1690148)
#include <iostream>
#include <cstdio>
#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()
{
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
int len1, len2;
len1 = citesteLinie(s1 + 1, fin);
len2 = citesteLinie(s2 + 1, fin);
kmp(len1, len2);
fprintf(fout, "%d\n", npotriviri);
for(int i = 1; i <= npotriviri; ++i)
fprintf(fout, "%d ", 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;
}
}
int citesteLinie(char s[], FILE *f){
int len;
fgets(s, 2000000, f);
len = strlen(s);
if(s[len - 1] == '\n'){
s[len - 1] = '\0';
--len;
}
return len;
}