CodeForces 314 B.Sereja and Periods 思维+简单dp【转】

迷南。 2022-06-13 11:07 179阅读 0赞

Description

Let's introduce the designation ![95ac7a780c428d495603e843532f92b9f87bde72.png][], where *x* is a string, *n* is a positive integer and operation " + " is the string concatenation operation. For example, \[*abc*, 2\] = *abcabc*.

We'll say that string *s*can be obtained from string *t*, if we can remove some characters from string *t* and obtain string *s*. For example, strings *ab* and *aсba* can be obtained from string *xacbac*, and strings *bx* and *aaa* cannot be obtained from it.

Sereja has two strings, *w* = \[*a*, *b*\] and *q* = \[*c*, *d*\]. He wants to find such maximum integer *p*(*p* > 0), that \[*q*, *p*\] can be obtained from string *w*.

Input

The first line contains two integers *b*, *d*(1 ≤ *b*, *d* ≤ 107). The second line contains string *a*. The third line contains string *c*. The given strings are not empty and consist of lowercase English letters. Their lengths do not exceed 100.

Output

In a single line print an integer — the largest number *p*. If the required value of *p* doesn't exist, print 0.

Sample Input

Input

10 3
    abab
    bab

Output

题解：

自己用模拟做了n遍都没过。。惭愧，看了博客才恍然大悟要用dp，附上神犇博客http://blog.csdn.net/yskyskyer123/article/details/52352107 ，因为懒得讲解了，到博客里看吧

引用：

令dp\[x\]表示c串的第x字符开始匹配，匹配完一个字符串a后，能够匹配多少个整字符串c，并且nex\[x\]代表下次开始匹配的位置。

代码：

#include<stdio.h>
    #include<cstring>
    #include<string>
    #include<iostream>
    #include<algorithm>
    #include<math.h>
    #include<queue>
    #include<stack>
    using namespace std;
    char s1[1005],s2[1005];
    int dp[105];
    int nex[105];
    int b,d,len1,len2;
    void cope(int x)
    {
        dp[x]=0;
        int use=0;
        nex[x]=x;
        while(use<len1)
        {
            if(s1[use]==s2[nex[x]])
            {
                nex[x]++;
                if(nex[x]==len2)
                {
                    dp[x]++;
                    nex[x]=0;
                }
            }
            use++;
        }
    }
    int main()
    {
        int i,j;
        while(scanf("%d%d",&b,&d)!=EOF)
        {
            scanf("%s%s",s1,s2);
            len1=strlen(s1);
            len2=strlen(s2);
            for(i=0;i<len2;i++)
                cope(i);
            int x=0,num=0;
            for(i=0;i<b;i++)
            {
                num+=dp[x];
                x=nex[x];
            }
            num/=d;
            printf("%d\n",num);
        }
        return 0;
    }

[95ac7a780c428d495603e843532f92b9f87bde72.png]: https://vj.wust.edu.cn/ojFiles/codeforces/predownloaded/95/ac/95ac7a780c428d495603e843532f92b9f87bde72.png