KMP算法在圆周率中查找生日

KMP算法不多说，算是经典算法里难啃的硬骨头。

理论上圆周率小数点后10e位包含了任意8位数的组合，即所有人的生日。存放圆周率的文件用y-cruncher软件生成，这个软件可以生成包含pi在内的各种常数，还可以进行压力测试。

 

 软件运行界面如图，生成10e位数字会提示内存不够，一般情况5000w就够用了。生成的文件在软件子目录下，可以转移到代码运行目录，也可以直接输入文件路径。

代码如下：

#include <iostream>
#include <string>
#include <fstream>
using namespace std;

int Index_KMP(string S, string T, int pos, int next[]) {
     /* 利用模式串T的next函数求T在主串S中的第pos个
        字符之后的位置的KMP算法。其中，T非空，
        1≤pos≤StrLength(S)*/
    int i = pos;
    int j = 1;
    while (i <= S.size() && j <= T.size()) {  //0下标存储字符串长度
        if (j == 0 || S[i - 1] == T[j - 1]) { ++i;  ++j; }  // 继续比较后继字符
            else  j = next[j];         // 模式串向右移动
        }
    if (j > T.size())
        return  i-T.size();    // 匹配成功
    else
        return 0;
} // Index_KMP

void get_next(string T, int next[]) {
     // 求模式串T的next函数值并存入数组next
     int i = 1;
     next[1] = 0;
     int j = 0;

     while (i < T.size()) {
        if (j == 0 || T[i - 1] == T[j - 1])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else  j = next[j];
    }
} // get_next

int main () {
    int next[9],pos;
    ifstream infile;
    string birth,S;
    //cout <<  "请输入文件路径：";
    //cin >> sdir;
    cout << "请输入8位生日：";
    cin >> birth;
    get_next(birth, next);
    infile.open("Pi.dat");   //读取文件
    if(!infile.is_open())
        return 0;
    infile >> S;
    pos = Index_KMP(S, birth, 0, next);
    if(pos != 0)
        cout << "匹配成功：匹配串中第" << pos << "个字符为模式串开始" << endl;
    else
        cout << "查询无结果，请更新文件！" <<endl;
    infile.close();

    return 0;
}

　　这里我直接用一个string接受了文件内容，如果文件内容很大的话建议分多次读取。

 

 

--- end ---