此题要找到第一个突破口．题意要求将s2重复n2次后再最多重复M次，使得其结果能够contained in S1．由此可以迅速反应到，本质就是求s2能重复多少次使得contained in S1．如果s2能最多重复Ｒ次使得contained in S1，显然M=R/n2
于是接下来考虑S1=s1*n1里有多少个重复的s2．原则上，这只要顺着S1过一遍就得到答案了．另外，因为S1本质是n1个s1串联，我们不需要显式地存储下整个S1，只需要一个指针不断地在s1里循环即可．于是第一个版本很容易写出来．这里用i表示S1里的index，x和y表示在s1和s2里面的index.
int getMaxRepetitions(string s1, int n1, string s2, int n2)
{
int L1=s1.size();
int L2=s2.size();
int y = 0;
int x;
int count=0;
for (int i=0; i<L1*n1; i++)
{
x = i%L1;
y = y%L2;
if (s1[x]==s2[y])
{
if (y==L2-1)
count++;
y++;
}
}
return count/n2;
}上面的这个版本会超时．很容易看出，因为S1是有很多相同的s1串联组成的，所以Ｓ1里面极有可能有许多连续循环出现的片段，而这些片段本身已经是s2（或连续的几个s2）的一个扩集．如果我们重复对这些每个片段再进行逐一扫描，而没有充分利用这些重复信息，就会有不必要的计算．
于是我们考虑应该如何找出这些＂连续循环出现的基本片段＂．如前所述，每个片段应该恰好对应s2（或连续的几个s2）的一个扩集．在S1里这个片段不断循环，对应s2也不断地循环．于是我们考虑追踪一个从s2到s1的映射．如果s2[y]==s1[x]（表示这对字符匹配）并且这个映射之前曾经出现过，那么我们就可以认为从上次出现映射的位置ｉ开始，到现在的位置ｉ，这之间经过了S1的一个＂循环片段＂，相应地对应于经历了若干个s2．由此我们可以知道S1的这个循环片段的长度，以及这个长度内对应有几个s2的出现．我们在之后直接利用这个循环片段的长度为单位来往后推进，而不用再逐字地分析．
我设置了这个映射所需要保留的两个信息．第一个PairPos[y][x]表示出现s2[y]==s1[x]这个映射时的i，即对应的S1的index；第二个PairCount[y][x]表示出现s2[y]==s1[x]这个映射时总共计数了多少个s2．于是，当我们发现这个映射第二次出现时，说明这个＂循环片段＂的长度就是p=i-PairPos[y][x]，在这个循环长度里出现了t=count-PairCount[y][x]个s2．此后，我们对于i的推进，就以＂循环片段＂的长度为p单位，而count的增长也就以t为单位．