POJ1699 HDU 1560 Best Sequence(AC自动机 最短路)

曾写过迭代加深搜索的方法,现在使用在AC自动上跑最短路的方法

dp[i][j]表示状态为到节点i,模式串是否包含的状态为j的最短串的长度,则状态转移方程为:

dp[nx][ny] = min(dp[x][y] + 1) , 其中nx为x后继结点,ny为从y转移过来的新状态,更新时加入队列

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<string>
using namespace std; int Hash[128];
typedef long long LL; const int N = 150, CH = 4, INF = 0x3F3F3F3F;
int n, cnt;
struct Trie{
Trie *next[CH];
Trie *fail;
int id;
}tree[N], *q[50000]; int chi[N][CH];
int sum[N];
int dp[N][1024];
bool inq[N][1024]; class ACauto{
private:
int nxt;
Trie *root; public:
ACauto(){
root = &tree[0];
nxt=0;
memset(&tree[0], 0, sizeof(Trie));
} void insert(string s, int id){
Trie *p = root;
for(int i = 0; i < s.size(); i++){
int c = Hash[s[i]];
if(!p -> next[c]){
memset(&tree[++nxt], 0, sizeof(Trie));
p -> next[c] = &tree[nxt];
p -> next[c] -> id = nxt;
}
p = p -> next[c];
}
sum[p->id] = 1 <<id;
} void build(){
int front = 0, rear = 0;
q[rear++] = root;
root -> fail = NULL;
while(front < rear){
Trie *cur = q[front++]; if(cur -> fail){
sum[cur->id] |= sum[cur->fail ->id];
} for(int i = 0; i < CH; i++){ Trie *son = cur -> next[i];
Trie *tp = (cur == root)? root: cur -> fail->next[i];
if(son == NULL){
cur -> next[i] = tp;
}else{
son -> fail = tp;
q[rear++] = son;
}
son = cur -> next[i];
chi[cur->id][i] = son->id;
}
}
} void solve(){
memset(dp, 0x3F, sizeof(dp));
memset(inq, 0, sizeof(inq));
queue<int> q;
dp[0][0] = 0;
inq[0][0] = 1;
int st = 1 << cnt;
q.push(0);
while(!q.empty()){
int u = q.front();
q.pop();
int x = u / st;
int y = u % st;
inq[x][y] = 0;
for(int i = 0 ; i < CH; i++){
int nx = chi[x][i], ny = y | sum[chi[x][i]];
if(dp[nx][ny] > dp[x][y] + 1){
dp[nx][ny] = dp[x][y] + 1;
if(!inq[nx][ny]){
q.push(nx * st + ny);
inq[nx][ny] = 1;
}
}
}
}
int ans = INF;
for(int i = 0; i <= nxt; i++){
ans = min(ans, dp[i][st - 1]);
}
printf("%d\n", ans); } }; char str[100];
int main(){
Hash['A'] = 0;
Hash['C'] = 1;
Hash['G'] = 2;
Hash['T'] = 3;
int t;
cin>>t;
while(t--){
int n;
cin>>n;
set<string> st;
for(int i = 0; i < n; i++){
string str;
cin>>str;
st.insert(str);
}
ACauto ac;
memset(sum, 0, sizeof(sum)); cnt = 0;
for(set<string>::iterator it = st.begin(); it != st.end(); it++){
ac.insert(*it, cnt++);
}
ac.build();
ac.solve();
} return 0;
}

  

上一篇:对武汉-and-IT软件开发的看法


下一篇:C# 生成字符串的 CheckSum