使用KMP算法实现串匹配你在课堂上想必已经烂熟于心了，不过咱们先来聊一聊圆周率π。有的人猜想，无理数π的小数部分包含了宇宙中的大秘密，比如你的生日、你男朋友/女朋友的生日，甚至是你的银行卡的账号密码。将它穷尽是一件不可能的事情，但是我们可以对前面的部分进行考察。
在这个题目中，不允许使用编程语言内置的字符串匹配算法，例如C语言中的strcmp。

如果你想查找自己的π信息，可以登录网站The Pi-Search Page

输入格式:

输入为两行，第一行为圆周率小数部分的节选s，长度不超过106；第二行是要查找的数字串t，长度不超过106。可以假设，输入都是0~9这样的数字。

输出格式:

输出t在s中首次出现的位置。如果t未在s中出现，则输出-1，以换行结尾。

输入样例1:

821999052039574422
19990520

输出样例1:

2

输入样例2:

881994082555083527588321827035
19940825

输出样例2:

2

输入样例3:

141592653
264

输出样例3:

-1

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> computeLPS(const string& pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);
    int len = 0;
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

int KMPSearch(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> lps = computeLPS(pattern);

    int i = 0, j = 0;
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        if (j == m) {
            return i - j;  // Pattern found
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;  // Pattern not found
}

int main() {
    string text, pattern;
    getline(cin, text);
    getline(cin, pattern);

    int result = KMPSearch(text, pattern);
    cout << result << endl;

    return 0;
}