0

假设您有一个包含以下字符串的文件

a a a b a a b a a b b a b

您无权访问该文件，但有一个函数 FetchNextChar() 一次提供一个字符。

并且要匹配的模式是 a a b

您如何计算点击总数？

这就是我的想法。

  1. 如果获取的字符是模式 ('a') 的第一个字符，则将其添加到队列
  2. 如果它与模式的下一个字符匹配，则开始为下一个字符附加/创建一个链表

所以在第一次获取之后我们有

Pattern -a 
Queue - a 

Then 

Pattern -a  a 
Queue[0] a->a 
Queue[1] a


3rd 
Pattern    a    a    b
Queue[0]   a -->a--> a    //doesn't match, dequeue
Queue[1]        a-> a
Queue[2]             a

我认为这可行，但我看到的问题是，如果有多个字符与模式的第一个字符匹配，我会继续添加到队列中，因此继续增加列表。

有什么想法吗？

4

2 回答 2

3

您可以使用基于状态的算法：

三态算法

我们可以看到，每次'b'读取 a 时，我们都会继续，state=0如果我们继续，则模式出现的次数会增加 1 state=2。当 a被读取时，我们显然'a'会进入下一个以 为界的状态。state=2

这是一个实现算法的python脚本 

stream = ['a','a','a','b','a','a','b','a','a','b','b','a','b']

state = 0 
nbMatch = 0

for c in stream:
    if c=='a':
        if state==0 or state==1:
            state = state+1
        #if state == 2: state=2
    else: #c=='b'
        if state==2:
            nbMatch = nbMatch+1
        state = 0
    print c, "   state=", state
print nbMatch
于 2013-03-01T08:58:42.757 回答
2

这可以使用Rabin–Karp 算法为滑动窗口计算 a有效地解决rolling hash，一个简单的滚动哈希函数是对字符的 ASCII 码求和，但是你可以使用这个数组primes来减少冲突，我已经测试了这些素数并在大而相似的字符串和模式匹配上给了我一些冲突：

primes[] = {13 , 7963 , 17443 , 27527 , 37879 , 48673 , 59407 , 70729 , 81883 , 93251 , 104789 , 116531 , 128239 , 139969 , 151783 , 163883 , 176159 , 188029 , 200257 , 212447 , 224831 , 237283 , 249517 , 262217 , 274661 , 287173};

这是上述算法打印匹配数的伪代码：

stream = "aaabaabaabbab";
pattern = "aab";
queue window;

patternHash = 0;
for ch in pattern:
    patternHash = patternHash + primes[ch - 'a']

first = readFromStream(stream)
window.enqueue(first)
windowHash = primes[first - 'a']
for i = 0 to pattern.size():
    ch = readFromStream(stream)
    window.enqueue(ch)
    windowHash = windowHash + primes[ch - 'a']

count = 0
for i = pattern.size() to stream.size():
    if windowHash == patternHash
        if window == pattern
            count = count + 1
    ch = readFromStream(stream)
    window.enqueue(ch)
    windowHash = windowHash - primes[window.first() - 'a']
    windowHash = windowHash + primes[ch - 'a']
    window.dequeue()

print count
于 2013-03-02T21:25:49.880 回答