#include<stdio.h>#include<string.h>#define ULL unsigned long longint seed=100;char s1[10005],s2[1000005];int main(){    int t;    scanf("%d",&t);    while(t--)    {        scanf("%s%s",s1,s2);        int len1=strlen(s1),len2=strlen(s2);        ULL a1=0,a2=0,l1=1;        for(int i=0;i<len1;++i)        {            a1=a1*seed+(s1[i]-‘A‘+1);            l1*=seed;        }        for(int i=0;i<len1;++i)        {            a2=a2*seed+(s2[i]-‘A‘+1);        }        int ans=0;        if(a1==a2) ans++;        for(int i=len1;i<len2;++i)        {            a2=a2*seed+(s2[i]-‘A‘+1)-l1*(s2[i-len1]-‘A‘+1);            if(a2==a1) ans++;        }        printf("%d\n",ans);    }    return 0;}

// Memory   Time// 1347K     0MS// by : Snarl_jsb// 2014-10-04-11.53#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define N 1000010#define LL long longusing namespace std;char s1[10005],s2[1000005];vector<int> next;void GetNext(char s[]){    int len=strlen(s),k=0;    next.clear();    next.push_back(0);    for(int i=1;i<len;++i)    {        while(k!=0&&s[i]!=s[k])            k=next[k-1];        if(s[i]==s[k])            k++;        next.push_back(k);    }}int KMP(char s1[],char s2[]){    int l1=strlen(s1),l2=strlen(s2);    int k=0,ans=0;;    for(int i=0;i<l2;++i)    {        while(k!=0&&s2[i]!=s1[k])            k=next[k-1];        if(s2[i]==s1[k])            k++;        if(k==l1)        {            ans++;            k=next[k-1];        }    }    return ans;}int main(){    int t;    scanf("%d",&t);    while(t--)    {        scanf("%s%s",s1,s2);        int len1=strlen(s1),len2=strlen(s2);        GetNext(s1);        printf("%d\n",KMP(s1,s2));    }    return 0;}

// Memory   Time// 1347K     0MS// by : Snarl_jsb// 2014-09-30-11.01#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define LL long longusing namespace std;const int N = 1001000;char str[N];struct node{    node *next[30];     //  每个结点都对应30个字母的指针    node *fail;     //      失配指针    int count;      //    node()      //  构造函数初始化    {        for(int i = 0; i < 30; i++)            next[i] = NULL;        count = 0;        fail = NULL;    }}*q[N];node *root;int head, tail;void Insert(char *str) //   插入单词.相当于构建一个Trie树{    node *p = root;    int i = 0, index;    while(str[i]) {        index = str[i] - 65; //  转化为相对数字来存        if(p->next[index] == NULL) // 该字母未插入过            p->next[index] = new node();    //  为该字母申请一个结点        p = p->next[index];     //   移至下一个        i++;    }    p->count++;     //      记录该结点的单词总共插入的次数}void build_ac_automation(node *root)        //      bfs建立fail指针{    root->fail = NULL;    q[tail++] = root;    while(head < tail) {        node *temp = q[head++];        node *p = NULL;        for(int i = 0; i < 30; i++) {            if(temp->next[i] != NULL) {                if(temp == root) temp->next[i]->fail = root;                else {                    p = temp->fail;                    while(p != NULL) {                        if(p->next[i] != NULL) {                            temp->next[i]->fail = p->next[i];                            break;                        }                        p = p->fail;                    }                    if(p == NULL) temp->next[i]->fail = root;                }                q[tail++] = temp->next[i];            }        }    }}int total=0;int Query(node *root)       //  匹配 + 统计{    int i = 0, cnt = 0, index;    node *p = root;    int idx=0;    while(str[i])    {        index = str[i] - 65;        while(p->next[index] == NULL && p != root) //前缀是相同的，所以不管哪个指针走到了count不为0的结点上，那么该结点所代表的单词就匹配成功            p = p->fail;//失配情况下，p指针指向p->fail.(相当于KMP的next数组)        p = p->next[index];//由于现在所在的位置是父节点，所以需要向下移动一个位置        if(p == NULL)            p = root; //如果匹配失败，移动到root，重新开始匹配        node *temp = p;//        while(temp != root && temp->count != -1)  //统计--如果匹配成功,那么count>1，表示该结点代表的单词数量;否则表示该结点没有单词        {            if(temp->count>0)            {                cnt ++; //统计该单词出现的次数            }//            temp->count = -1;   //标记为-1，表示该单词已经加入了cnt中，下次就不用重复统计            temp = temp->fail;//判断整条链上的匹配情况        }        i++;    }    return cnt;}int main(){    int t;    cin>>t;    while(t--)    {        head=tail=0;        root=new node();        scanf("%s",str);        Insert(str);        build_ac_automation(root);        scanf("%s",str);//        Query(root);        printf("%d\n",Query(root));    }    return 0;}