前言：
眼前兄弟们对“算法lcs”大体比较看重，你们都需要知道一些“算法lcs”的相关知识。那么小编同时在网摘上汇集了一些对于“算法lcs””的相关知识，希望同学们能喜欢，朋友们一起来了解一下吧！背景
桌面凌乱，想找一个文件找半天找不到，今天小编分享一个利用LCS算法，寻找文件名有共同公有字符串的文件，并将之一键整体到同一文件夹；代码里面已经做了十分详细的说明，大家可以根据自己的文件命名习惯修改代码，以达到更精准的文件归档；
凌乱的电脑桌面
软件是界面如图：LCS算法原理：
(1) 以行和列将两个字符串组成矩阵，即一个字符串为行一个为列。
(2) 比较每个节点行列处字符是否相同，如相同则为 1。
(3) 找出值为 1 的最长对角线，即是我们要找的最长公共子串。
人 民 共 和 时 代
中 0, 0, 0, 0, 0, 0
华 0, 0, 0, 0, 0, 0
人 1, 0, 0, 0, 0, 0
民 0, 1, 0, 0, 0, 0
共 0, 0, 1, 0, 0, 0
和 0, 0, 0, 1, 0, 0
国 0, 0, 0, 0, 0, 0
进一步优化算法，将相同字符节点(1)的值加上左上角(d[i-1, j-1])的值，可获得计算出公用子串的长度。接下来便只需以行号和最大值为条件即可截取最大子串。
人 民 共 和 时 代
中 0, 0, 0, 0, 0, 0
华 0, 0, 0, 0, 0, 0
人 1, 0, 0, 0, 0, 0
民 0, 2, 0, 0, 0, 0
共 0, 0, 3, 0, 0, 0
和 0, 0, 0, 4, 0, 0
国 0, 0, 0, 0, 0, 0
具体实现代码：
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Windows.Forms;
using System.IO;
namespace FolderArrangement
{
public partial class Form1 : Form
{
string BaseDir = string.Empty;
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
BaseDir = Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory);
//这里为了测试，我在桌面新建了一个Test文件夹，大家看是需要整理哪里就自己修改
BaseDir += "\\Test";
}
private void label1_Click(object sender, EventArgs e)
{
}
private void button1_Click(object sender, EventArgs e)
{
//if (textBox1.Text == "") MessageBox.Show("请输入文件夹名称");
try
{
DirectoryInfo dirInfo = new DirectoryInfo(BaseDir);
FileInfo[] files = dirInfo.GetFiles();
if (textBox1.Text != "")
{
if (!Directory.Exists(Path.Combine(BaseDir, textBox1.Text.Trim()))) Directory.CreateDirectory(Path.Combine(BaseDir, textBox1.Text.Trim()));
}
//利用两边循环，一一对比，寻找与目标文件名有公字符串的文件
foreach (FileInfo file in files)
{
bool has_same = false;
string Dir_path = string.Empty;
string fileName = file.Name;
string fileName_Noextension = Path.GetFileNameWithoutExtension(Path.Combine(file.DirectoryName, fileName));
// 如果是有输入文件夹，那么直接将所有文件名含有文件夹名称的都放进去
if (textBox1.Text != "")
{
if (fileName.Contains(textBox1.Text.Trim()))
{
Dir_path = Path.Combine(BaseDir, textBox1.Text.Trim());
file.MoveTo(Path.Combine(Dir_path, file.Name));
}
}
else
{
foreach (FileInfo file_in in files)
{
if (file_in != file)
{
string fileName_in = file_in.Name;
string fileName_Noextension_in = Path.GetFileNameWithoutExtension(Path.Combine(file_in.DirectoryName, fileName_in));
string comm_str = LCS(fileName_Noextension, fileName_Noextension_in);
//公字符串长度要大于2，因为如果等于1的话，归档错的概率太高 公串在各文件名中所占比例不应太低
//这里是主要筛选条件，大家根据自己需要自己定义啊；每个人文件命名习惯不一样可能规律不一样
if (comm_str.Length >= 2 && ((float)(comm_str.Length) / (float)(fileName_Noextension.Length) >= 0.3 || (float)(comm_str.Length) / (float)(fileName_Noextension_in.Length) >= 0.3))
{
Dir_path = Path.Combine(BaseDir, comm_str);
if (!Directory.Exists(Dir_path)) Directory.CreateDirectory(Dir_path);
if (Directory.Exists(Dir_path))
{
try
{ file_in.MoveTo(Path.Combine(Dir_path, file_in.Name)); }
catch (Exception ex)
{
MessageBox.Show(ex.Message);
}
has_same = true;
}
}
}
}
if (has_same)
{
try
{
file.MoveTo(Path.Combine(Dir_path, file.Name));
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
}
}
}
//这里很多文件在前面的逻辑中已经移动至文件夹中了，所以一边循环后需要重新获取一下files对象
files = dirInfo.GetFiles();
}
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
}
}
//找两个文件名的最大公字符串 利用LSC算法
private string LCS(string str1, string str2)
{
if (str1 == str2)
return str1;
else if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
return null;
var d = new int[str1.Length, str2.Length];
var index = 0;
var length = 0;
for (int i = 0; i < str1.Length; i++)
{
for (int j = 0; j < str2.Length; j++)
{
//左上角
var n = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1, j - 1] : 0;
//当前节点值等于“左上角的值+1”：“0”
d[i, j] = str1[i] == str2[j] ? n + 1 : 0;
//如果是最大值，记录该值和行号
if (d[i, j] > length)
{
length = d[i, j];
index = i;
}
}
}
return str1.Substring(index - length + 1, length);
}
}
}
END
手KEY不易，各位看客老爷路过点个关注，小编每天都会分享C/C++、C#等相关编程知识~~~
标签： #算法lcs
