unixfy - C++博客

C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合

:: 管理

posts - 183, comments - 10, trackbacks - 0

朴素贝叶斯分类器的实现

摘要: //// Email: goonyangxiaofang@163.com// QQ: 591247876//// Naive Bayes//// 输入样例// ... 阅读全文

posted @ 2011-03-06 19:13 unixfy 阅读(2203) | 评论 (0) | 编辑收藏

编辑距离 + 交换操作

编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
　　以上的问题可以用众所周知的动态规划解决，现在的问题是：如果新加入一种编辑操作：交换相邻的两个字符；求两个字符串之间的编辑距离。

#include <iostream>

#include <cstring>

using namespace std;

#define T(t) cout << #t": " << t << endl;

int a[1002][1002];

char s1[1002], s2[1002];

int main()

{

cin >> s1 >> s2;

for (int i = 0; i < 1002; ++i) {

a[i][0] = i;

a[0][i] = i;

}

int n1 = strlen(s1), n2 = strlen(s2);

int r, t, c1;

for (int i = 1; i <= n1; ++i) {

for (int j = 1; j <= n2; ++j) {

r = (a[i-1][j] < a[i][j-1] ? a[i-1][j] : a[i][j-1]) + 1;

if (s1[i-1] != s2[j-1]) {

t = a[i-1][j-1] + 1;

}

else {

t = a[i-1][j-1];

}

r = (r < t ? r : t);

if (i >= 2 && j >= 2) {

c1 = a[i-2][j-2] + 1;

r = (r < c1 ? r : c1);

}

a[i][j] = r;

}

}

cout << a[n1][n2] << endl;;

}

无法 AC，但是找不到错误，先记下。
http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1093

posted @ 2011-03-04 22:41 unixfy 阅读(728) | 评论 (0) | 编辑收藏

C++ 博客的第一篇

刚刚开通 C++ 博客
本来有一个博客，为了提高专业性和扩大交流面，特在此开通一个

这里将记述我的计算机方面的学习、研究、工作以及生活等
包括
程序设计语言
数据结构与算法
自然语言处理
信息抽取
还有其他的计算机方面

还有我的生活

以上，2010-09-25

posted @ 2010-09-25 15:15 unixfy 阅读(130) | 评论 (0) | 编辑收藏

仅列出标题