L - Mahdi And The Teddy Bear 字符串模拟
Time goes so quickly; remember Bakkar’s &Maymona’s anniversary two years ago whenBakkar bought a smartphone as a surprise gift forMaymona? Well Maymona had also a joyful surprise forBakkar.Maymona was pregnant.
Months later Maymona gave birth to a beautiful baby and they decided to call himMahdi. They were really so excited about their first child and decided to do their best to raise him up well.Mahdi is now about one year old and started to learn how to talk. AsBakkar &Maymona are geeks they had a very creative idea to teachMahdi how to talk and evaluate his progress.
Simply they programmed a little teddy bear to speak so Mahdi can repeat after him. When Mahdi repeats what the teddy bear just said it recognises the word and analyse it. And as we all know its very natural that kids don’t spell all letters at the beginning. So whatBakkar & Maymona thought to evaluate the correctness and progress of whatMahdi says is to check if the workMahdi repeats after the teddy bear is a subsequence of the original word the teddy bear just said. To evaluateMahdi’s progress the teddy bear defines a subsequence of a stringy if it can be produced by deleting some of the characters iny. For example, "ace" is a subsequence of "adcbe" but not a subsequence of "bcae". IfMahdi spells a subsequence it is considered to be a positive indicator thatMahdi is progressing. To motivateMahdi when he spells something correctly according to what we mentioned; if he spells a subsequence of the original word the teddy bear would respond with ‘bravo’ and start clapping, Otherwise he would repeat the word again several times until soMahdi can take his time practicing.
The teddy bear is programmed in a very simple and creative way. He says random words based on an equation thatBakkar &Maymona invented. They specify a starting character to start the word, the length of the word, adder and multiplier. Simply the word is generated as follows:
s0 = starting character
si = char((pos(si - 1) * multiplier + i * adder) % 26)
Where:
pos(a) = 0, pos(b) = 1, ....pos(z) = 25
char(0)= a, char(1)= b,.....char(25)= z
Hmmmmm, Bakkar & Maymona are so busy; Bakkar at his work andMaymona taking care of the house andMahdi. And as you are one of their best friends and still single and have some spare time you proposed to program the teddy bear for them. Besides you are the voice recognition geek among their friends ;).
For simplicity the words Mahdi repeats will be generated using the same equation the teddy bear uses.
The first line will be an integer T (1 ≤ T ≤ 10) the number of test cases. Each test case will start by a line containing 1 character and 3 integers (length, multiplier, adder) for the stringS as described above (1 ≤ length(S) ≤ 107). The next line will contain a single integerN (1 ≤ N ≤ 104) the number of stringsMahdi repeats. The nextN lines each contain 1 character and 3 integers (length, multiplier, adder) for the stringLi as described above. The starting character will be a lowercase character, (1 ≤ length(Li) ≤ 100),
1 ≤ multiplier, adder ≤ 1000.
For each test, For each test case print a single line containing "Case n:" (without the quotes) where n is the test case number (starting from 1) followed by N lines each containing either "BRAVO" (without quotes) ifLi is a subsequence of S andMahdi is making a progress or "REPEAT" (without quotes) otherwise.
1 a 100 13 37 3 a 11 11 311 b 9 13 22 d 5 31 12
Case 1: REPEAT REPEAT BRAVO
for input d 5 31 12, the string will be
s0 = d
s1 = char((pos(d) * 31 + 1 * 12)%26) = char((3 * 31 + 1 * 12)%26) = char(105%26) = char(1) = b
s2 = char((pos(b) * 31 + 2 * 12)%26) = char((1 * 31 + 2 * 12)%26) = char(55%26) = char(3) = d
s3 = char((pos(d) * 31 + 3 * 12)%26) = char((3 * 31 + 3 * 12)%26) = char(129%26)= char(25) = z
s4 = char((pos(z) * 31 + 4 * 12)%26) = char((25 * 31 + 4 * 12)%26) = char(823%26) = char(17) = r
so the string is "dbdzr"
Warning: large Input/Output data, be careful with certain languages.
题意：
给出一个递推公式，可以求出任意长度的字符串
然后题目间接提供一个主串，N个查询子串，问此子串是否是主串的子串
例如ace 是 主串 alkjcsdje的子串
题解：
昨天晚上了试了无数种方法，从二维空间缩小到了一维空间，从二维dp降解到了一维dp，但是最后还是超了
看了官方题解才知道需要全部一起查询，而且查询子串只需要记录我们搜索到最后一个字母，想想确实如此
主串不需要预处理，查询子串也一样，全部同时在线处理
在主串逐个计算出一个个字母的时候，然后搜索是否有某子串当前搜索的最后一个字母与之相同
若相同就将此子串计算下一个字母，并且保存下来，并且把之前的旧子串清除（更新操作）
若没有就将主串计算出下一个字母
vector< pair<int,int> >A[26];
注意：
字母相同的情况，使用上叙的STL可以巧妙的处理好
#include<vector>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int T,cases=1;
freopen("mahdi.in","r",stdin);
scanf("%d",&T);
while(T--)
{
string S;///主串
int L,N;///主串长度，查询个数
int R[2];///常量multiplier和adder
cin>>S>>L>>R[0]>>R[1]>>N;
vector< pair<int,int> >A[26];
vector<int>last(N);///记录查询串的最后一个字母position
vector<int>Ls(N);///记录查询的串的长度
vector<int>Rs[2];
Rs[0].resize(N);///设置一维大小，表示第i个查询的multiplier
Rs[1].resize(N);///设置二维大小，表示第i个查询的adder
//~~~~~~~~~~~~~~~输出并且记录需要查询的~~~~~~~~~~~~~~~~~~//
string s;
for(int i=0;i<N;i++){
cin>>s>>Ls[i]>>Rs[0][i]>>Rs[1][i];
last[i]=s[0]-'a';
A[s[0]-'a'].push_back(make_pair(0,i));
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//
int x;
vector<bool>ans(N,false);///记录第i个串是否可以在主串中查找得到，后者为默认值
for(int i=0;i<L;i++)
{
vector<pair<int,int> > upd=A[S[i]-'a'];///主串的当前字母S[i]，需要在子串A中查找
A[S[i]-'a'].clear();
for(int i=0;i<upd.size();i++)
{
upd[i].first++;///上面已经查找到当前一个， 然后更新下一个字母
int id =upd[i].second;
if(Ls[id]==upd[i].first){///判断是否已经查找到整个子串
ans[id]=true;
continue;
}
//-------------子串更新操作---------------------//
x=(last[id]*Rs[0][id]+upd[i].first*Rs[1][id])%26;
last[id]=x;
A[x].push_back(upd[i]);
//----------------------------------------------//
}
//-------------主串更新操作---------------------//
x=((S[i]-'a')*R[0]+(i+1)*R[1])%26;
x+=(x<0?26:0);
S+=(char)('a'+x);
//----------------------------------------------//
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//
printf("Case %d:\n",cases++);
for(int i=0;i<N;i++)
puts(ans[i]?"BRAVO":"REPEAT");
}
return 0;
}