<div class="plm" style="text-align: center; font-size: 12pt; color: rgb(34, 34, 34); clear: both;"><div class="ptt" id="problem_title" style="font-size: 18pt; font-weight: bold; color: blue; padding: 10px;"><span style="color: green;">G - </span>Oulipo</div><span id="crawlSuccess" class="crawlInfo" style="display: inline;"><strong>Time Limit:</strong><span id="timeLimit">1000</span>MS <strong>Memory Limit:</strong><span id="memoryLimit">32768</span>KB <strong>64bit IO Format:</strong><span id="_64IOFormat">%I64d & %I64u</span></span><div id="problem_opt" style="font-size: 12px; margin-top: 10px;"><a target=_blank id="submit" class="ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only" role="button" style="display: inline-block; position: relative; padding: 0px; margin-right: 0.1em; cursor: pointer; vertical-align: middle; overflow: visible; font-family: Verdana, Arial, sans-serif; font-size: 1em; border: 1px solid rgb(211, 211, 211); color: rgb(85, 85, 85); border-radius: 4px; background: url(http://acm.hust.edu.cn/vjudge/jquery-ui-1.11.1.custom/images/ui-bg_glass_75_e3e4f8_1x400.png) 50% 50% repeat-x rgb(227, 228, 248);"><span class="ui-button-text" style="display: block; padding: 0.4em 1em;">Submit</span></a> <a target=_blank id="problem_status" href="http://acm.hust.edu.cn/vjudge/contest/123546#status//G/0" class="ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only" role="button" style="display: inline-block; position: relative; padding: 0px; margin-right: 0.1em; cursor: pointer; vertical-align: middle; overflow: visible; text-decoration: none; font-family: Verdana, Arial, sans-serif; font-size: 1em; border: 1px solid rgb(211, 211, 211); color: rgb(85, 85, 85); border-radius: 4px; background: url(http://acm.hust.edu.cn/vjudge/jquery-ui-1.11.1.custom/images/ui-bg_glass_75_e3e4f8_1x400.png) 50% 50% repeat-x rgb(227, 228, 248);"><span class="ui-button-text" style="display: block; padding: 0.4em 1em;">Status</span></a></div></div><div style="color: rgb(34, 34, 34); font-family: Verdana, Arial, sans-serif; font-size: 14px; width: 960px; margin: auto;"><div id="desc_G_0" class="desc_template"><div class="vj_description"><p class="pst" style="font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue; margin-bottom: 0px;">Description</p><div class="textBG" style="border-radius: 10px; padding: 10px; border-style: dotted; border-width: 2px; background-color: rgb(234, 235, 255);"><div class="panel_content">The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e'. He was a member of the Oulipo group. A quote from the book:
Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…
Perec would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given “word” as possible. Our task is to provide the jury with a program that counts these occurrences, in order to obtain a ranking of the competitors. These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive 'T's is not unusual. And they never use spaces.
So we want to quickly find out how often a word, i.e., a given string, occurs in a text. More formally: given the alphabet {'A', 'B', 'C', …, 'Z'} and two finite strings over that alphabet, a word W and a text T, count the number of occurrences of W in T. All the consecutive characters of W must exactly match consecutive characters of T. Occurrences may overlap.
</div><div class="panel_bottom"> </div></div></div><div class="vj_input"><p class="pst" style="font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue; margin-bottom: 0px;">Input</p><div class="textBG" style="border-radius: 10px; padding: 10px; border-style: dotted; border-width: 2px; background-color: rgb(234, 235, 255);"><div class="panel_content">The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
One line with the word W, a string over {'A', 'B', 'C', …, 'Z'}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W).
One line with the text T, a string over {'A', 'B', 'C', …, 'Z'}, with |W| ≤ |T| ≤ 1,000,000.
</div><div class="panel_bottom"> </div></div></div><div class="vj_output"><p class="pst" style="font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue; margin-bottom: 0px;">Output</p><div class="textBG" style="border-radius: 10px; padding: 10px; border-style: dotted; border-width: 2px; background-color: rgb(234, 235, 255);"><div class="panel_content">For every test case in the input file, the output should contain a single number, on a single line: the number of occurrences of the word W in the text T.
</div><div class="panel_bottom"> </div></div></div><div class="vj_sampleInput"><p class="pst" style="font-family: Arial, Helvetica, sans-serif; font-size: 18pt; font-weight: bold; color: blue; margin-bottom: 0px;">Sample Input</p><div class="textBG" style="border-radius: 10px; padding: 10px; border-style: dotted; border-width: 2px; background-color: rgb(234, 235, 255);"><div class="panel_content"><pre style="white-space: pre-wrap; word-wrap: break-word;"><div style="font-family: 'Courier New', Courier, monospace;">3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN </div>
Sample Output
1
3
0
这道题的大体意思呢，，也就是说有多组数据输入，，然后每组数据有两行字符串，问在第二个字符串中有多少第一个字符串，，最后输出其数量。。
这道题的关键是两个字符串的长度所限定的范围太大，，如果直接暴力的话。。必定会超时，，所以这道题应该用到KMP算法。。这个的课程推荐网易云课堂数据结构的KMP算法。。
这道题的输入最好是scanf（“%s”，x）；否则就算应用了KMP算法，，也还是有可能超时的。。
注：望大神给出宝贵建议。
#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <algorithm>#include <cmath>#include <queue>using namespace std;<span style="color:#ffcc99;"></span>char a[10010],b[1000010];int pp[10010];void Get_next(){ int len = strlen(a); int i = 0,j = -1; pp[0] = -1; while(i<len) { if(j==-1||a[i] == a[j]) { i++; j++; if(a[i]!=a[j]) pp[i] = j; else pp[i] = pp[j]; } else j = pp[j]; }}//KMPsolve（）这个函数是主要的实现代码，他调用了Get—next（）函数，，是为了得到非著名的next数组。。int KMPsol(){ Get_next(); int ans = 0; int l = 0,k = 0; int len = strlen(a); int len1 = strlen(b); while(l<len1) { if(k == -1||b[l] == a[k]) { l++; k++; } else { k = pp[k]; } if(k == len) { k = pp[k]; ans++; } } cout<<ans<<endl;}int main(){ int n; scanf("%d",&n); while(n--) { scanf("%s",a); scanf("%s",b); KMPsol(); } return 0;}