manacher.cpp
Bài toán
Tìm xâu con liên tiếp đối xứng dài nhất.
Độ phức tạp
O(n)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
bool maximize(int &a, int b) {
if (a < b)
a = b;
else
return false;
return true;
}
void prepare(char a[], char b[]) {
int cnt = 0;
b[++cnt] = '#';
for (int i = 1; a[i]; i++) {
b[++cnt] = a[i];
b[++cnt] = '#';
}
b[++cnt] = 0;
b[0] = '^';
}
int manacher(char b[]) {
int C = 1, R = 1, n = strlen(b + 1);
int *P = new int[n + 2], r = 0;
for (int i = 2; i < n; i++) {
int i_mirror = 2 * C - i;
P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;
while (b[i - 1 - P[i]] == b[i + 1 + P[i]]) P[i]++;
maximize(r, P[i]);
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
delete[] P;
return r;
}
#define N 50004
char a[N], b[2 * N];
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n >> (a + 1);
prepare(a, b);
cout << manacher(b) << endl;
}
Mô tả
void prepare(char* a, char* b)
Tạo xâu b bằng cách chèn các kí tự # vào giữa mỗi cặp kí tự liên tiếp trong xâu a. Ví dụ, a="aabc" thì b="#a#a#b#c#"
int R, C, P[]
Giả sử ta đang xét tới vị trí i, xâu con đối xứng dài nhất có tâm x bắt đầu từ ll[x] và kết thúc tại rr[x], thì R = max { rr[x], 0<x<i }, C là chỉ số nhỏ nhất mà rr[C]=R. P[x] = rr[x]-x+1 (khoảng cách từ rr[x] đến x trên xâu b, hay độ dài xâu đối xứng có tâm ở vị trí x/2 trên xâu a)
Nhận xét
Code này đã được dùng để nộp cho một bài tập trên SPOJ.
Phần nhập xuất đã được thay đổi để phù hợp với nội dung.
Tham khảo
http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html