HDU 2594データ構造のKMP
クリックしてリンクを開く
二つの列は、最初の列の最初の列と第二の列のマッチングの最長の長さを求めます.
考え方:二つの列を合わせて、合併した後の長さはlenで、KMPのnext配列を求めて、next[len]は後の方が前の方との整合度を表しています.つまり、一致する位置です.そして、検討して処理してください.
二つの列は、最初の列の最初の列と第二の列のマッチングの最長の長さを求めます.
考え方:二つの列を合わせて、合併した後の長さはlenで、KMPのnext配列を求めて、next[len]は後の方が前の方との整合度を表しています.つまり、一致する位置です.そして、検討して処理してください.
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=100010;
const int mod=10007;
char str1[maxn],str2[maxn];
int Next[maxn];
void makenext(int m){
int i=0,j=-1;
Next[i]=-1;
while(i<m){
if(j==-1||str1[i]==str1[j])
Next[++i]=++j;
else j=Next[j];
}
}
//int KMP(int n,int m){
// int i=0,j=0,ans=0;
// while(i<n){
// if(j==-1||str2[i]==str1[j]) i++,j++;
// else j=Next[j];
// if(j==m){
// ans++;j=Next[j-1];i--;
// }
// }
// return ans;
//}
int main(){
int n,m,x,a,b;
while(scanf("%d%d",&m,&n)!=-1){
init(n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&num[0][i],&lv[i],&x);
for(int j=1;j<=x;j++){
scanf("%d%d",&a,&b);
num[a][i]=b;
}
}
int max1,ans1=inf;
for(int i=1;i<=n;i++){
max1=lv[i];
for(int j=1;j<=n;j++){
if(lv[j]>max1||(max1-lv[j])>m)
v[j]=1;
else v[j]=0;
}
int ans2=dijkstra(n,0);
if(ans1>ans2)
ans1=ans2;
}
printf("%d
",ans1);
}
return 0;
}