palindrome code in C times out in program challenge?

Question

Hello I am making a code in C to find the value of the last sequence of palindromes of a specified size (d) and I need to optimize this code as it is for an exercise platform called URI Online Judge and is giving Time Limit exceeded.

https://www.urionlinejudge.com.br/judge/en/problems/view/1686

Given a string s[1..N], we define a palindromic sequence of length p and displacement d (1 <= p <= d) as a sequence of k (k >= 1) disjoint substrings of s (each of which is a palindrome of length p) distant d characters from each other.

More formally, it can be written as the following sequence of disjoint substrings of s : A= (s[i..i+p-1], s[i+d..i+d+p-1], s[i+2d..i+2d+p-1], ...), where each element of A is a palindrome of length p. Recall that a string is called a palindrome if it reads the same forwards and backwards.

The value of a palindromic sequence is the total number of characters from string s it uses (i.e., if the sequence has k palindromes of length p, its value is k*p). Given a fixed displacement value D, calculate the largest value of a palindromic sequence contained in a string S.

Input
Each test case is described using two lines. The first line contains two integers N and D (1 <= N <=10^5), 1 <= D <=10^5) representing respectively the length of the string S and the required displacement value. The next line contains the string S of length N consisting only of lowercase letters.

The last test case is followed by a line containing two zeros.

Output
For each test case output a line with the maximum value of a palindromic sequence with displacement D in string S.

Samples
Input
5 1
abbbc
Output
5

#include <stdio.h> char palavra[100000]; int palindrome(const int inicio, const int fim) { if (inicio >= fim) { return 1; } if (palavra[inicio] != palavra[fim - 1]) { return 0; } return palindrome(inicio + 1, fim - 1); } int maior_sequencia(const int n, const int d) { int valor = 0, temp; int i, j; for (i = 1; i <= d; i++) { temp = 0; for (j = 0; j < n; j += d) { if (palindrome(j, j + i)) { temp++; } } if (temp * i > valor) { valor = temp * i; } } return valor; } int main() { int n, d; while (1) { scanf("%d %d", &n, &d); if (n == 0 || d == 0) { return 0; } scanf("%s", palavra); printf("%d\n", maior_sequencia(n, d)); } return 0; } 

edit: Now i have a functional code, but give Time Limit exceeded again :/

edit 2: I added another version of the code, how could I optimize one of these two versions?

Answer 1

General Observations

It might be better to use an iterative solution rather than a recursive solution for this problem. Recursion can be expensive in terms of memory resources for the stack and it could also result in stack overflow. Calling a function is more expensive in terms of time than looping through a string as well. If the calling function created a reverse string it might be possible to use strcmp() or strstr() in the palindrome() function, either of those functions are very fast. It would also be faster to base the palindrome() function on strings rather than indexes.

While the program description uses n and d it would better to use more descriptive names in the program to make it more readable, examples might be length and displacement.

Since this question is performance based I won't recommend this, but memory for palavra be allocated in the while (1) { loop in main() since the length of the string is read in during each iteration.

Since English variable and function names are generally considered a global programming standard it might be better to use English variable and function names. I can figure out inicio and fim as start and end, but I don't have a clue what palavra or maior_sequencia (for maior_sequencia I'm guessing that it means major sequence). This is especially true since the problem statement is in English.

Avoid Global Variables

It is very difficult to read, write, debug and maintain programs that use global variables. Global variables can be modified by any function within the program and therefore require each function to be examined before making changes in the code. In C and C++ global variables impact the namespace and they can cause linking errors if they are defined in multiple files. The answers in this stackoverflow question provide a fuller explanation.

The variable palavra should be declared in main and passed into functions as necessary.

Declare Variables as Necessary

The original version of C required all variables to be declared at the top of a logic block, but this is no longer the case. In almost all programming languages it is now considered better to declare and initialize variables as they are needed. In the C programming language they need to be initialized because no local variable have a default value assigned. Each variable should be declared and initialized on its own line to make the code easier to read, write and maintain. In the function maior_sequencia the variables i and j can be defined in their respective loops:

int maior_sequencia(const size_t length, const size_t displacement, char *palavra) { size_t valor = 0; size_t temp = 0; for (size_t i = 1; i <= displacement; i++) { temp = 0; for (size_t j = 0; j < length; j += displacement) { if (palindrome(j, j + i, palavra)) { temp++; } } if (temp * i > valor) { valor = temp * i; } } return valor; } 

Use Unsigned Integer Based Variables for Indexes and Sizes

Rather than using integers that can go negative for indexes and sizes it is better to use types such as size_t which are based on unsigned integers. The type size_t is what is returned by the sizeof(OBJECT) function as an example.

Magic Numbers

There are Magic Numbers function (100000), it might be better to create symbolic constants for them to make the code more readable and easier to maintain. These numbers may be used in many places and being able to change them by editing only one line makes maintenance easier.

Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them. There is a discussion of this on stackoverflow.

Don't Ignore Library Function Return Values

The function scanf() returns an integer that indicates the number of values read or end of file (EOF). This value can be used to control the while loop in main() rather than having the while (1) loop with a break.

#define MAX_LENGTH 10000 int main() { size_t length = 0; size_t displacement = 0; while (scanf("%d %d", &length, &displacement) != EOF) { char palavra[MAX_LENGTH + 1]; if (scanf("%s", palavra) == EOF) { break; } else { printf("%d\n", maior_sequencia(length, displacement, palavra)); } } return 0; }