Pagini recente » Cod sursa (job #2088545) | Cod sursa (job #1411843) | Cod sursa (job #1635731) | Cod sursa (job #1159232) | Cod sursa (job #1011540)
#include <stdio.h>
#include <stdlib.h>
char s1[2000001];
char s2[2000001];
int pi[2000001];
int solutions[2000001];
int n=1,m=1;
int mini(int a, int b){
if (a<b)
return a;
else
return b;
}
void readData(){
char c;
int i=1;
fgets(s1, sizeof(s1), stdin);
i=1;
while ((s1[i] <='Z' && s1[i] >= 'A') || (s1[i] <= 'z' && s1[i] >= 'a') || (s1[i] >= '0' && s1[i] <= '9') ){
i++;
}
m = i;
fgets(s2, sizeof(s2), stdin);
i=1;
while ((s2[i] <='Z' && s2[i] >= 'A') || (s2[i] <= 'z' && s2[i] >= 'a') || (s2[i] >= '0' && s2[i] <= '9') ){
i++;
}
n = i;
for (int i=n-1; i>=0; i--){
s2[i+1] = s2[i];
}
for (int i=m-1; i>=0; i--){
s1[i+1] = s1[i];
}
}
void buildPrefixTable(){
//build the prefix table for the first, smaller string
int k=0;
int q = 1;
pi[1] = 0;
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 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++;
}
}
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;
}