Data una sequenza di numeri di lunghezza N, come faccio a trovare la sottosequenza di lunghezza K che si ripete più volte all’interno?
Esempio N=10, K=4
Input: 9 2 5 0 1 2 5 0 1 1
Output: 2 5 0 1
Una soluzione possibile è quella di utilizzare la ricorsione
#include <stdio.h>
#include <string.h>
int findMax(char str[],int n,int k,char strMax[],int pointer);
int countSubstr(char string[], char substring[]);
int main()
{
int n=10;
int k=4;
int pointer=0;
char str[100] = "9250125011";
char strMax[100];
strcpy(strMax,str);
int max=findMax(str,n,k,strMax,pointer);
printf("result\n");
printf("%d\n",max);
printf("%s",strMax);
return 0;
}
int findMax(char str[],int n,int k,char strMax [],int pointer){
int max=0;
if((k+pointer)>n){
return max;
}
char item[k+1];
memcpy( item, &str[pointer], k );
item[k] = '\0';
printf("%s\n",item);
int occ=countSubstr(str,item);
printf("%d\n",max);
printf("------\n");
max=findMax(str,n,k,strMax,pointer+1);
if(occ<max){
return max;
}else{
strcpy(strMax,item);
return occ;
}
}
int countSubstr(char string[], char substring[])
{
int subcount = 0;
size_t sub_len = strlen(substring);
if (!sub_len) return 0;
for (size_t i = 0;string[i];) {
size_t j = 0;
size_t count = 0;
while (string[i] && string[j] && string[i] == substring[j]) {
count++;
i++;
j++;
}
if (count == sub_len) {
subcount++;
count = 0;
}
else {
i = i - j + 1;
}
}
return subcount;
}