題目：
解題思路：
代碼實(shí)現(xiàn)：
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define MAX_N 500000
// 字符串存儲(chǔ)
char str[MAX_N + 5];
// 定義鏈?zhǔn)角跋蛐?struct Edge {
int to, next;
} g[MAX_N << 2];
int head[MAX_N + 5], cnt = 0;
// 廣搜隊(duì)列
int dis[MAX_N + 5], vis[MAX_N + 5];
queue<int> q;
// 加邊函數(shù)
inline void add(int a, int b) {
g[++cnt] = {b, head[a]};
head[a] = cnt;
}
void expand(char *str, int i, int j) {
while (i >= 0 && str[i] == str[j]) {
add(i, j + 1);
i -= 1, j += 1;
}
return ;
}
// 從0到strlen(str)的最短路
void spfa(int s) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[s] = 0;
vis[s] = 1;
q.push(s);
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = g[i].next) {
int to = g[i].to;
if (dis[x] + 1 >= dis[to]) continue;
dis[to] = dis[x] + 1;
if (!vis[to]) q.push(to), vis[to] = 1;
}
}
return ;
}
int main() {
cin>>str;
for (int i = 0; str[i]; i++) {
expand(str, i, i);
expand(str, i, i + 1);
}
spfa(0);
cout << dis[strlen(str)] - 1 << endl;
return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
