当前位置:网站首页>Linear DP acwing 899 Edit distance
Linear DP acwing 899 Edit distance
2022-07-02 12:43:00 【T_ Y_ F666】
linear DP AcWing 899. Edit distance
Original link
Algorithm tags
Dynamic programming linear DP
Code
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 1005, INF = 0x3f3f3f3f;
int n,m;
char s[N][N], a[N];
int f[N][N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
int dis(char a[], char b[]){
rep(i, 0, strlen(a+1)+1){
f[i][0]=i;
}
rep(i, 0, strlen(b+1)+1){
f[0][i]=i;
}
rep(i, 1, strlen(a+1)+1){
rep(j, 1, strlen(b+1)+1){
f[i][j]=min(f[i-1][j]+1, f[i][j-1]+1);
f[i][j]=min(f[i][j], f[i-1][j-1]+(a[i]!=b[j]));
}
}
return f[strlen(a+1)][strlen(b+1)];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
n=read(),m=read();
rep(i, 0, n){
scanf("%s", s[i]+1);
}
while(m--){
int ans=0;
scanf("%s", a+1);
int b=read();
rep(i, 0, n){
if(dis(s[i], a)<=b){
ans++;
}
}
printf("%lld\n", ans);
}
return 0;
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
- FBX import under ue4/ue5 runtime
- About asp Net MVC project in local vs running response time is too long to access, the solution!
- Efficiency comparison between ArrayList and LinkedList
- spfa AcWing 851. spfa求最短路
- Hash table acwing 840 Simulated hash table
- 8A 同步降压稳压器 TPS568230RJER_规格信息
- JS6day(DOM结点的查找、增加、删除。实例化时间,时间戳,时间戳的案例,重绘和回流)
- H5 to app
- Mongodb redis differences
- Leetcode - Sword finger offer 59 - I, 59 - II
猜你喜欢
Counting class DP acwing 900 Integer partition
Deep copy event bus
spfa AcWing 852. SPFA judgement negative ring
Async/await asynchronous function
2.7 binary tree, post order traversal - [FBI tree]
Anti shake throttle
架构师必须了解的 5 种最佳软件架构模式
bellman-ford AcWing 853. Shortest path with side limit
js3day(数组操作,js冒泡排序,函数,调试窗口,作用域及作用域链,匿名函数,对象,Math对象)
js1day(输入输出语法,数据类型,数据类型转换,var和let区别)
随机推荐
Simple understanding of ThreadLocal
Shutter encapsulated button
移动式布局(流式布局)
js 迭代器 生成器 异步代码处理 promise+生成器 -> await/async
Is the neural network (pinn) with embedded physical knowledge a pit?
The coloring method determines the bipartite graph acwing 860 Chromatic judgement bipartite graph
Anti shake throttle
Lekao: 22 year first-class fire engineer "technical practice" knowledge points
Drools terminates the execution of other rules after executing one rule
Embedded Software Engineer career planning
Wechat official account payment prompt MCH_ ID parameter format error
spfa AcWing 851. SPFA finding the shortest path
Heap acwing 839 Simulated reactor
JSON序列化 与 解析
FBX import under ue4/ue5 runtime
This "little routine" is set on the dough cake of instant noodles. No wonder programmers are always hungry
Counting class DP acwing 900 Integer partition
Lekao.com: experience sharing of junior economists and previous candidates in customs clearance
绕过ObRegisterCallbacks需要驱动签名方法
Docker compose configuration mysql, redis, mongodb