LPS 문제 풀이 및 C언어구현 코드

1. 문제 정의

LPS 문제는 가장 긴 팰린드롬 부분 문자열(Longest Palindromic Substring)을 찾는 문제이다. 팰린드롬이란 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 의미하며, 이는 특정 유사성이나 대칭성을 가진 문자열의 구성을 나타낸다. 예를 들어, `racecar`나 `madam`과 같은 문자열이 이에 해당한다. LPS 문제는 주어진 문자열 내에서 이와 같은 성질을 가진 가장 긴 부분 문자열을 찾아야 하는 문제로, 다양한 응용 분야에서 중요한 역할을 한다. 이 문제는 문자열 처리와 관련된 알고리즘적 접근 방식을 요구하며, 효율적인 해결 방안을 찾기 위해서는 여러 가지 방법론을 고려할 필요가 있다. 문제가 제기된 배경은 문자열 관련 과제가 빈번하게 등장하는 컴퓨터 과학 분야의 특성과 관련이 깊다. 예를 들어, 텍스트 편집기에서 입력된 단어의 수정을 관리하거나 DNA 서열 분석에서 특정 패턴의 동질성을 검사하는 데 있어 팰린드롬 발견의 필요성이 대두된다. 이렇게 문자열의 대칭성을 파악하는 것은 이미지 처리, 자연어 처리, 그리고 데이터 검색 등 여러 분야에서 핵심적인 작업으로 자리 잡고 있다. LPS 문제는 단순히 결과를 산출하는 것뿐만 아니라…