//数据结构病毒检测利用串

//在D盘创建text.txt文件，text.out 文件

//代码如下

#define SIZE 80
#define OK = 1

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

typedef struct Chunk {
    char ch[SIZE];
    struct Chunk* next;
}Chunk;

typedef struct {
    Chunk* head, * tail;//串的头指针和尾指针
    int curlen;//当前串的长度
};

typedef struct {
    char ch[SIZE +1];//存储串的一维数组
    int length;
}SString;

int Slength(SString e) {
    int n = 0, i = 1;
    while (e.ch[i]) {
        n++;
        i++;
    }
    return n;
}

int Index_BF(SString S, SString T, int pos) {
    int i = pos;
    int j = 1;
    int SL = Slength(S);//测试串
    int TL = Slength(T);//病毒串
    cout << SL << " " << TL << endl;
    while (i <= SL && j <= TL) {
        if (S.ch[i] == T.ch[j]) {
            ++i;
            ++j;
        }
        else {
            i = i - j + 2;
            j = 1;
        }
    }
    cout << i << " " << j << TL << endl;
    if (j > TL)return (i - TL);
    else return 0;
}

int main() {
    ifstream infile("D:\\text1.txt");//以文件的方式来读取要使用的数据
    ofstream outfile("D:\\text1_out.txt");
    if (!infile && !outfile) {
        cout << "文件读取失败！";
        return 0;
    }
    else cout << "文件读取成功！" << endl;
    SString S, T;//S为病毒串，T为待检测串
    SString V;
    int num;
    infile >> num;
    int flag = 0;
    int pos = 1;
    cout << "有" << num << "组数据待检测！" << endl;
    while (num--) {

        infile >> T.ch + 1;//病毒串
        infile >> S.ch + 1;//测试串
        int flag;;
        int m = Slength(S);
        S.length = m;
        V.ch[2 * m + 1] = '\0';
        for (int i = 0; i < m; i++) {
            V.ch[i + 1] = S.ch[i + 1];
        }
        for (int i = m + 1, j = 1; j <= m; j++)//字符串拼接
            V.ch[i++] = S.ch[j];
        flag = Index_BF(V, T, 1);
        if (flag) {
            outfile << S.ch + 1 << "    " << T.ch + 1 << "   " << "YES" << endl;
            cout <<S.ch + 1 << "    " << T.ch + 1 << "    " << "YES"<< endl;
        }
        else {
            outfile << S.ch + 1 << "    " << T.ch + 1 << "   " << "NO" << endl;
            cout << S.ch + 1 << "    " << T.ch + 1 << "    " << "NO" << endl;
        }
        cout << "flag is " << flag << endl;
    }
    cout << "检测成功！";
    return 0;
}