HDOJ 2087カット布(KMP)
2082 ワード
布を切る
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11305 Accepted Submission(s): 7260
Problem Description
1枚の花の布の条、中にはいくつかの図案があって、もう1枚の直接利用できる小さな飾りの条があって、中にもいくつかの図案があります.与えられたスプラインと小さなスプラインについて、スプラインからできるだけいくつかの小さなスプラインを切ることができるかを計算します.
Input
入力にはいくつかのデータが含まれていて、それぞれペアで現れた花の布条と小さな飾り条で、その布条はすべて可視ASCII文字で表されて、可視ASCII文字は何個あって、布条の模様も何種類の模様があります.ストライプと小さなストライプは1000文字を超えません.#文字に遭遇した場合は、作業は行われません.
Output
柄布から切り取ることができる最小の数を出力し、1枚もない場合は0を正直に出力し、結果ごとに改行します.
Sample Input
Sample Output
kmp簡単な問題、注意とhdoj 1686 Oulipoは異なり、親列の文字はサブ列と重複して一致することはできません.
コードは次のとおりです.
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11305 Accepted Submission(s): 7260
Problem Description
1枚の花の布の条、中にはいくつかの図案があって、もう1枚の直接利用できる小さな飾りの条があって、中にもいくつかの図案があります.与えられたスプラインと小さなスプラインについて、スプラインからできるだけいくつかの小さなスプラインを切ることができるかを計算します.
Input
入力にはいくつかのデータが含まれていて、それぞれペアで現れた花の布条と小さな飾り条で、その布条はすべて可視ASCII文字で表されて、可視ASCII文字は何個あって、布条の模様も何種類の模様があります.ストライプと小さなストライプは1000文字を超えません.#文字に遭遇した場合は、作業は行われません.
Output
柄布から切り取ることができる最小の数を出力し、1枚もない場合は0を正直に出力し、結果ごとに改行します.
Sample Input
abcde a3 aaaaaa aa #
Sample Output
0 3
kmp簡単な問題、注意とhdoj 1686 Oulipoは異なり、親列の文字はサブ列と重複して一致することはできません.
コードは次のとおりです.
<span style="font-size:12px;">#include<cstdio>
#include<cstring>
char s[1010],str[1010];
int next[1010],lena,lenb,ans;
void getnext()
{
int i=0,j=-1;
next[0]=-1;
while(i<lenb)
{
if(j==-1||str[i]==str[j])
next[++i]=++j;
else
j=next[j];
}
}
void kmp()
{
int i=0,j=0;
while(i<lena)
{
if(j==-1||s[i]==str[j])
{
i++;
j++;
if(j==lenb)
{
ans++;
j=0;
}
}
else
j=next[j];
}
}
int main()
{
while(scanf("%s",s)&&strcmp(s,"#")!=0)
{
scanf("%s",str);
lena=strlen(s);
lenb=strlen(str);
ans=0;
getnext();
kmp();
printf("%d
",ans);
}
return 0;
}</span>