Pagini recente » Cod sursa (job #495966) | Cod sursa (job #1930879) | Cod sursa (job #2563558) | Cod sursa (job #1653864) | Cod sursa (job #2807046)
// This program was written on 23.11.2021
// for problem strmatch
// by Mircea Rebengiuc
#include <stdio.h>
#include <ctype.h>
#define MAXN 2000000
#define MAXOUT 1000
char text[MAXN];
char pat[MAXN + 2];
int lps[MAXN];
int match[MAXN];
int nmatch;
FILE *fin, *fout;
static inline int fgetint(){
int n = 0, ch, semn = 1;
while( isspace(ch = fgetc(fin)) );
if( ch == '-' ){
semn = -1;
ch = fgetc(fin);
}
do
n = n * 10 + ch - '0';
while( isdigit(ch = fgetc(fin)) );
return n * semn;
}
int main(){
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
int n, m, i, j;
fscanf(fin, "%s %s", pat, text);
n = -1;
while( isalnum(pat[++n]) );
m = -1;
while( isalnum(text[++m]) );
//printf("n = %d | m = %d\n", n, m);
// get lps
lps[0] = 0;
for( i = 1 ; i < n ; i++ ){
j = lps[i - 1];
while( j > 0 && pat[j] != pat[i] )
j = lps[j - 1];
lps[i] = j + (pat[i] == pat[j]);
}
// search for pattern in text
j = nmatch = 0;
for( i = 0 ; i < m ; i++ ){
while( j > 0 && pat[j] != text[i] )
j = lps[j - 1];
if( text[i] == pat[j] ){
if( (++j) == n ){
match[nmatch++] = i - n + 1;
j = lps[j - 1];
}
}
}
fprintf(fout, "%d\n", nmatch);
nmatch = MAXOUT < nmatch ? MAXOUT : nmatch;
for( i = 0 ; i < nmatch ; i++ )
fprintf(fout, "%d ", match[i]);
fputc('\n', fout);
fclose(fin);
fclose(fout);
return 0;
}