Boyer-Moore算法实现陷入循环致整数溢出问题求助

问题现象 #

实现的Boyer-Moore字符串匹配算法在匹配到模式串后会陷入无限循环，最终变量i超出整数范围导致程序崩溃。例如输入主文本maatemaatika、模式串aa时，预期输出位置1和6，但当前代码无法正常执行。

原代码 #

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp6
{
    public class TraziUzorak
    {
        private string glavniTekst; // 主文本

        public void UnosGlavnog()
        {
            Console.WriteLine("Unesite glavni tekst:"); // 输入待搜索的主文本
            glavniTekst = Console.ReadLine();
        }

        public int[] Trazi(string uzorak)
        {
            List<int> pozicije = new List<int>();

            int m = uzorak.Length;
            int n = glavniTekst.Length;

            int[] pomak = PrecomputeShift(uzorak);

            int i = 0;
            while (i <= n - m)
            {
                int j = m - 1;

                while (j >= 0 && uzorak[j] == glavniTekst[i + j])
                    j--;

                if (j < 0)
                {
                    pozicije.Add(i);
                    // 原错误逻辑：可能导致i不增加甚至减少
                    i += (i + m < n) ? m - pomak[glavniTekst[i + m]] : 1;
                }
                else
                {
                    i += Math.Max(1, j - pomak[glavniTekst[i + j]]);
                }
            }

            return pozicije.ToArray();
        }

        private int[] PrecomputeShift(string uzorak)
        {
            int[] pomak = new int[256];

            for (int i = 0; i < 256; i++)
            {
                pomak[i] = uzorak.Length;
            }

            for (int i = 0; i < uzorak.Length - 1; i++)
            {
                pomak[uzorak[i]] = uzorak.Length - i - 1;
            }

            return pomak;
        }
    }
    internal class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Unesite broj ponavljanja traženja:"); // 输入搜索次数
            int brojPonavljanja = int.Parse(Console.ReadLine());

            TraziUzorak traziUzorak = new TraziUzorak();

            for (int i = 0; i < brojPonavljanja; i++)
            {
                traziUzorak.UnosGlavnog();

                Console.WriteLine("Unesite uzorak koji želite tražiti:"); // 输入待搜索的模式
                string uzorak = Console.ReadLine();

                int[] rezultati = traziUzorak.Trazi(uzorak);

                if (rezultati.Length > 0)
                {
                    foreach (int pozicija in rezultati)
                    {
                        Console.WriteLine(pozicija);
                    }
                }
                else
                {
                    Console.WriteLine("nema");

                }

                Console.WriteLine();
                Console.ReadKey();
            }
        }
    }
}

问题根源 #

匹配成功后的i更新逻辑存在错误：
当i + m < n时，计算m - pomak[glavniTekst[i + m]]，如果该值为0或负数，i会停止增加甚至减少，导致循环条件i <= n - m永远成立，陷入无限循环。

以示例输入为例：

• 模式串长度m=2，匹配到i=1时，i+m=3，主文本对应字符是t，pomak['t']=2（因为t不在模式串中，初始值为模式长度），所以m - pomak['t']=2-2=0，i +=0后i仍为1，循环无法推进。

修复方案 #

匹配成功后，必须保证i的增量为正，避免循环停滞。修改匹配成功分支的i更新逻辑，使用Math.Max(1, ...)确保增量至少为1：

if (j < 0)
{
    pozicije.Add(i);
    // 修复后：确保i至少增加1，避免循环停滞
    i += (i + m < n) ? Math.Max(1, m - pomak[glavniTekst[i + m]]) : 1;
}

修复后验证 #

输入示例：

1 # 搜索次数
maatemaatika # 待搜索的主文本
aa # 待查找的模式

输出结果：

1
6

程序可正常执行，无循环崩溃问题。

内容的提问来源于stack exchange，提问作者AcademicWeapon