Pagini recente » Cod sursa (job #2664145) | Cod sursa (job #1738989) | Cod sursa (job #1247092) | Cod sursa (job #3261520) | Cod sursa (job #1011507)
#include <stdio.h>
#include <stdlib.h>
char s1[2000001];
char s2[2000001];
int pi[2000001];
int solutions[2000001];
int mini(int a, int b){
if (a<b)
return a;
else
return b;
}
void readData(){
char c;
gets(s1, sizeof(s1), )
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 && 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++;
if (foundNr >= 1000){
break;
}
}
}
printf("%d\n", foundNr);
for (int i=0; i<mini(foundNr, 1000); i++){
printf("%d ", solutions[i]);
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
readData();
buildPrefixTable();
kmp();
return 0;
}