This is extension of the rep-string task from Rosette code. I do not only want to check if the input string is the shortest periodic string (rep-string) or not, but also check if it is preperiodic.
Periodic means, that a part must occur two or more times.
Input is a binary string (only 1 and 0 chars). It can be for example binary expansion of the fraction
Output is a formatted binary string: preperiod(period)
10101010 = (10) // periodic
10010101010 = 100(10) // preperiodic
11111111110 // aperiodic
Below is my C code. I use simple / naive string-search algorithm, and the code works well.
#include <stdio.h>
#include <string.h>
// array of strings for testing
char *strs[] = {
// aperiodic
"11111111110", // aperiodic
"011111111110",
"11000100000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001", // https://en.wikipedia.org/wiki/Liouville_number
"110001000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010", // https://en.wikipedia.org/wiki/Liouville_number + 0
"101", // aperiodic because only one and a half repetition, possibly periodic if longer string
// periodic
"0100100", // (010) preperiod = 0 period = 3, truncated
"00100100100100100100100100100100100100100100100100100100100100100100100100100", // (001) preperiod = 0 period = 3 truncated
"1001110011", // = (10011) preperiod = 0 period = 5
"1110111011", // = (1110) preperiod = 0 period = 4
"0010010010", /* 4 x 001 and truncated, last char can be from 001*/
"001001001", /* 4 x 001 */
"1111111111", // (1)
"11", // (1) periodic
"00", // (0) periodic
// preperiodic
"0100101101",
"00100100101", /* 4 x 001 but last 2 chars are NOT from 001 */
"100100100101", /* */
"01111111111", // 0(1) preperiodic
"001010101010101", // preperiodic = 0(01) = 1/6
"0100101010101010" // preperiodic = 010(01) = 7/24
};
//
// strstr : Returns a pointer to the first occurrence of str2 in str1, or a null pointer if str2 is not part of str1.
// size_t is an unsigned integer typ
// looks for the shortest substring !!!!!
// GivePeriod = repstr_shortest
// https://rosettacode.org/wiki/Rep-string#C
int GivePeriod(char *str)
{
if (!str) return 0; // if empty input
size_t sl = 1;
size_t sl_max = strlen(str)/2+1 ; // more then one repetition of periodic parts
while (sl < sl_max) {
if (strstr(str, str + sl) == str) // How it works ???? It checks the whole string str
return sl;
++sl;
}
return 0;
}
int FormatString(char *str){
int p; // offset or preperiod ( if period is found)
int pMax = strlen(str) ; // length without null character
int period = 0;
int preperiod = 0;
char *substr;
for (p=0; p < pMax; ++p ){
substr = str+p;
period = GivePeriod( substr);
if (period > 0 ) {
preperiod = p;
//printf("substring =\t%*s\t from position =%d has preperiod = %d\tperiod = %d\n", pMax, substr, p, preperiod, period ); // pring part of the string from p position to the end ( without last null character)
printf("%s = %.*s(%.*s) preperiod = %d\tperiod = %d\n", str, p, str, period, str+p, preperiod, period );
return period;
}
// else printf("substring =\t%*s\t from position = %d\t\n", pMax, substr, p); // pring part of the string from p position to the end ( without last null character)
}
printf("%s is aperiodic\n", str);
return 0;
}
int main(){
int iMax = sizeof(strs) / sizeof(strs[0]); // number of test values
int i; // test number = index of the array
for (i = 0; i < iMax; ++i) // check all test values
FormatString(strs[i]);
return 0;
}
To compile :
gcc p.c -Wall
to run:
./a.out
My output is:
11111111110 is aperiodic
011111111110 is aperiodic
11000100000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 is aperiodic
110001000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010 is aperiodic
101 is aperiodic
0100100 = (010) preperiod = 0 period = 3
00100100100100100100100100100100100100100100100100100100100100100100100100100 = (001) preperiod = 0 period = 3
1001110011 = (10011) preperiod = 0 period = 5
1110111011 = (1110) preperiod = 0 period = 4
0010010010 = (001) preperiod = 0 period = 3
001001001 = (001) preperiod = 0 period = 3
1111111111 = (1) preperiod = 0 period = 1
11 = (1) preperiod = 0 period = 1
00 = (0) preperiod = 0 period = 1
0100101101 = 0100(101) preperiod = 4 period = 3
00100100101 = 0010010(01) preperiod = 7 period = 2
100100100101 = 10010010(01) preperiod = 8 period = 2
01111111111 = 0(1) preperiod = 1 period = 1
001010101010101 = 0(01) preperiod = 1 period = 2
0100101010101010 = 010(01) preperiod = 3 period = 2
Questions:
- Can I do it better ?
- Can you give examples of strings for which my program fail ?
- Does this code follow common best practices?
Edit 1
notation:
- period = length of periodic ( repeating) part
- preperiod = length of part before periodic part
- periodic string : preperiod = 0, period > 0
- preperiodic string : preperiod > 0 and period > 0
- aperiodic string : perperiod = 0 and period = 0
Note the input string is finite ( = finite part of infinite string) so maybe in a longer input string period or preperiod will be > 0