Pagini recente » Cod sursa (job #2062139) | Cod sursa (job #2136842) | Cod sursa (job #459028) | Cod sursa (job #2373223) | Cod sursa (job #2487893)
#include <stdio.h>
#include <string.h>
#include <vector>
#define NMAX 2000000
char s1 [ NMAX + 1 ] ;
char s2 [ NMAX + 1 ] ;
std::vector <int> poz ;
int lsp [ NMAX + 1 ] ; // longest proper prefix that is also a suffix lol
int main () {
FILE *fin, *fout ;
fin = fopen ("strmatch.in", "r") ;
fout = fopen ("strmatch.out", "w") ;
int n, i, m, x, counter ;
fscanf (fin, "%s", s1+1) ;
fscanf (fin, "%s", s2+1) ;
n = strlen(s1+1) ;
m = strlen(s2+1) ;
lsp[0] = 0 ;
lsp[1] = 0 ;
for (i = 2 ; i <= n ; i++) {
x = lsp[i-1] ;
while (x > 0 && s1[x+1] != s1[i])
x = lsp[x] ;
if (s1[x+1] == s1[i])
lsp[i] = x + 1 ;
else
lsp[i] = 0 ;
}
x = 0 ;
counter = 0 ;
for (i = 0 ; i <= m ; i++) {
while (x > 0 && s1[x+1] != s2[i])
x = lsp[x] ;
if (s1[x+1] == s2[i])
x++;
else
x = 0 ;
if (x == n) {
counter++;
poz.push_back(i-n) ;
}
}
fprintf(fout, "%d\n", counter);
for (i = 0 ; i < poz.size() ; i++)
fprintf(fout, "%d ", poz[i]) ;
return 0 ;
}