查找匹配字符串算法
本文关键字：算法 字符串 查找 | 更新日期: 2023-09-27 18:10:12
我有很长的5个字符串(字符串的数量可能会改变)。这些字符串没有固定的格式。我将提供一个数字，这将表明子字符串的长度。我想找到与给定长度匹配的子字符串。例如，字符串是:
1. abcabcabc
2. abcasdfklop
字符串长度:3
给定这些值，输出将是这样的:
比赛# 1:
Matched string : "abc"
Matches in first string: 3
Matching positions: 0,3,6
Matches in second string: 1
Match positions: 0
比赛# 2:
Matched string : "bca"
Matches in first string: 2
Matching positions: 1,4
Matches in second string: 1
Match positions: 1
我设法在4 foreach语句中完成它。但在我看来，这太没有效率了。特别是当输入尺寸非常大的时候。有什么建议或简单的方法可以在c#中更有效地管理这个吗?
您可以使用后缀数组来完成此操作。(后缀树也可以很好地工作，但它们在实现时需要更多的空间、时间和注意。)
连接两个字符串，用两个字符串中都不存在的字符将它们分开。然后构建后缀数组。然后你可以读出你的答案。
标准后缀数组为您提供了一个按字典顺序排序的字符串后缀指针数组，以及一个"最长公共前缀长度"数组，该数组告诉您两个按字典顺序连续的后缀的最长公共前缀长度。
使用最长的公共前缀长度数组来获取你想要的信息是相当简单的;找出最长公共前缀长度数组的所有最大子数组，其中最长公共前缀长度至少为查询长度，然后，对于在第一个字符串和第二个字符串中都有匹配的每个子数组，报告适当的前缀并报告它出现K+1次，其中K是最大子数组的长度。
另一种更容易编码的方法是对适当长度的所有子字符串进行散列。您可以使用任何滚动散列函数轻松地做到这一点。为每个散列存储一个动态指针数组到字符串中;在对所有字符串进行散列后，遍历出现的所有散列并查找匹配项。你需要以某种方式处理假阳性;一种(概率)方法是使用多个哈希函数，直到假阳性概率小到可以接受的程度。另一种方法是直接比较字符串，这可能只在匹配很少的情况下才可以接受。
如果你设法做到这一点在4 foreach语句没有嵌套，那么你应该很好，你可能不需要优化。
我想试试这个。创建一个如下所示的结构
class SubString
{
string str;
int position;
}
将两个字符串划分为所有可能的子字符串，并将它们存储到一个数组中。复杂度为0 (n2)。
现在按字符串长度(O(n*log(n))复杂度)对这些数组排序，并遍历这两个数组以确定匹配。
你需要额外的结构来保存结果，这可能需要一些调整，但你知道这是怎么做的。
您可以使用后缀树的变体来解决此问题。http://en.wikipedia.org/wiki/Longest_common_substring_problem算法:查找两个字符串之间保持顺序的所有公共子字符串
如果使用非常大的字符串，内存可能成为一个问题。下面的代码查找最长的公共子字符串，并写入包含较小的公共子字符串的变量，但可以很容易地更改为将索引和长度压入列表，然后将其作为字符串数组返回。
这是Ashutosh Singh在https://iq.opengenus.org/longest-common-substring-using-rolling-hash/上重构的c++代码-这将在O(N * log(N)^2)时间和O(N)空间中找到子字符串
using System;
using System.Collections.Generic;
public class RollingHash
{
private class RollingHashPowers
{
// _mod = prime modulus of polynomial hashing
// any prime number over a billion should suffice
internal const int _mod = (int)1e9 + 123;
// _hashBase = base (point of hashing)
// this should be a prime number larger than the number of characters used
// in my use case I am only interested in ASCII (256) characters
// for strings in languages using non-latin characters, this should be much larger
internal const long _hashBase = 257;
// _pow1 = powers of base modulo mod
internal readonly List<int> _pow1 = new List<int> { 1 };
// _pow2 = powers of base modulo 2^64
internal readonly List<long> _pow2 = new List<long> { 1L };
internal void EnsureLength(int length)
{
if (_pow1.Capacity < length)
{
_pow1.Capacity = _pow2.Capacity = length;
}
for (int currentIndx = _pow1.Count - 1; currentIndx < length; ++currentIndx)
{
_pow1.Add((int)(_pow1[currentIndx] * _hashBase % _mod));
_pow2.Add(_pow2[currentIndx] * _hashBase);
}
}
}
private class RollingHashedString
{
readonly RollingHashPowers _pows;
readonly int[] _pref1; // Hash on prefix modulo mod
readonly long[] _pref2; // Hash on prefix modulo 2^64
// Constructor from string:
internal RollingHashedString(RollingHashPowers pows, string s, bool caseInsensitive = false)
{
_pows = pows;
_pref1 = new int[s.Length + 1];
_pref2 = new long[s.Length + 1];
const long capAVal = 'A';
const long capZVal = 'Z';
const long aADif = 'a' - 'A';
unsafe
{
fixed (char* c = s)
{
// Fill arrays with polynomial hashes on prefix
for (int i = 0; i < s.Length; ++i)
{
long v = c[i];
if (caseInsensitive && capAVal <= v && v <= capZVal)
{
v += aADif;
}
_pref1[i + 1] = (int)((_pref1[i] + v * _pows._pow1[i]) % RollingHashPowers._mod);
_pref2[i + 1] = _pref2[i] + v * _pows._pow2[i];
}
}
}
}
// Rollingnomial hash of subsequence [pos, pos+len)
// If mxPow != 0, value automatically multiply on base in needed power.
// Finally base ^ mxPow
internal Tuple<int, long> Apply(int pos, int len, int mxPow = 0)
{
int hash1 = _pref1[pos + len] - _pref1[pos];
long hash2 = _pref2[pos + len] - _pref2[pos];
if (hash1 < 0)
{
hash1 += RollingHashPowers._mod;
}
if (mxPow != 0)
{
hash1 = (int)((long)hash1 * _pows._pow1[mxPow - (pos + len - 1)] % RollingHashPowers._mod);
hash2 *= _pows._pow2[mxPow - (pos + len - 1)];
}
return Tuple.Create(hash1, hash2);
}
}
private readonly RollingHashPowers _rhp;
public RollingHash(int longestLength = 0)
{
_rhp = new RollingHashPowers();
if (longestLength > 0)
{
_rhp.EnsureLength(longestLength);
}
}
public string FindCommonSubstring(string a, string b, bool caseInsensitive = false)
{
// Calculate max neede power of base:
int mxPow = Math.Max(a.Length, b.Length);
_rhp.EnsureLength(mxPow);
// Create hashing objects from strings:
RollingHashedString hash_a = new RollingHashedString(_rhp, a, caseInsensitive);
RollingHashedString hash_b = new RollingHashedString(_rhp, b, caseInsensitive);
// Binary search by length of same subsequence:
int pos = -1;
int low = 0;
int minLen = Math.Min(a.Length, b.Length);
int high = minLen + 1;
var tupleCompare = Comparer<Tuple<int, long>>.Default;
while (high - low > 1)
{
int mid = (low + high) / 2;
List<Tuple<int, long>> hashes = new List<Tuple<int, long>>(a.Length - mid + 1);
for (int i = 0; i + mid <= a.Length; ++i)
{
hashes.Add(hash_a.Apply(i, mid, mxPow));
}
hashes.Sort(tupleCompare);
int p = -1;
for (int i = 0; i + mid <= b.Length; ++i)
{
if (hashes.BinarySearch(hash_b.Apply(i, mid, mxPow), tupleCompare) >= 0)
{
p = i;
break;
}
}
if (p >= 0)
{
low = mid;
pos = p;
}
else
{
high = mid;
}
}
// Output answer:
return pos >= 0
? b.Substring(pos, low)
: string.Empty;
}
}