String aba center palindrome center middle element odd length palindrome

1)

Since a palindrome can be both of even or odd length. So in a string of length N there can be potentially 2N-1 centers around which palindrome substring can be found. More precisely N odd-length palindrome centers , N-1 even-length palindromes.

Algorithm :

Let A be the given string.

For i= 1 to N

odd_max = Maximum{ odd_max, odd_L(i) }

Return Maximum { odd_max,even_max}

}

If( A[i-k] = A[i+k]){ length= length+2; }

else{ return length; }

Function even_L (int i) {

int k=0;

Else { return length; }

k=k+1;

Space complexity is O(1) as we just keeping the maximums.

Time complexity is O(n^2) .

The time complexity is clearly O(nm) since there are n ·m subproblems each of which is solved in constant time.

3)

Complexity is O(m^n)

5)

To conclude, we have that, after all xi have been processed, A is consistent with a satisfying assignment to φn. Note that the final A assigns every variable of φn, so it is a complete truth assignment; moreover, A must satisfy every conjunct of φn, one of which is the original formula φ. Hence, A is a satisfying assignment to φ.

The above algorithm makes O(n) calls to the SAT oracle and otherwise does O(n) work.