Pagini recente » Cod sursa (job #3281949) | Cod sursa (job #2717045) | Cod sursa (job #1200150) | Cod sursa (job #1927846) | Cod sursa (job #1011483)
#include <stdio.h>
#include <stdlib.h>
char s1[2000001];
char s2[2000001];
int pi[2000001];
int solutions[2000001];
void readData(){
char c;
int i=1;
s1[0] = ' ';
s2[0] = ' ';
do {
scanf("%c", &c);
s1[i++] = c;
} while (c != '\n');
s1[--i] ='\0';
i=1;
do {
scanf("%c", &c);
s2[i++] = c;
} while (c != '\n' && c != EOF);
s2[--i] ='\0';
}
void buildPrefixTable(){
//build the prefix table for the first, smaller string
int k=0;
int q = 1;
pi[1] = 0;
int m = strlen(s1) - 1;
for (q=2; q <=m; q++) {
while (k>0 && s1[k+1] != s1[q]){
k = pi[k];
}
if (s1[k+1] == s1[q]){
k++;
}
pi[q] = k;
}
}
void kmp(){
int foundNr = 0;
int n = strlen(s2) - 1;
int m = strlen(s1) - 1;
int q = 0;
for (int i=1; i<=n; i++){
while (q > 0 && s1[q+1] != s2[i]){
q = pi[q];
}
if (s1[q+1] == s2[i]){
q++;
if (q == m){
q = pi[q];
solutions[foundNr] = i - m;
foundNr++;
}
}
}
printf("%d\n", foundNr);
for (int i=0; i<foundNr; i++){
printf("%d ", solutions[i]);
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
readData();
buildPrefixTable();
kmp();
return 0;
}