剪花布条 HDU - 2087
题意:
给你一个文本串T,和一个模板串p。 要求你把T分割,分割成最多的p。
思路:
贪心分割即可。
AC
#include <iostream>
#include <cstring>
using namespace std
;
int nxt
[2000];
void getnxt(char *p
){
int m
=strlen(p
);
int i
=0,j
=-1;
nxt
[0]=-1;
while(i
<m
){
if(j
==-1||p
[i
]==p
[j
])nxt
[++i
]=++j
;
else j
=nxt
[j
];
}
}
int kmp(char *s
, char *p
){
int res
=0;
int i
=0, j
=0;
int n
=strlen(s
),m
= strlen(p
);
while(i
<n
){
if(j
==-1||s
[i
]==p
[j
])i
++,j
++;
else j
=nxt
[j
];
if(j
==m
)j
=0,res
++;
}
return res
;
}
int main()
{
char p
[2000],s
[2000];
while(cin
>>s
){
if(s
[0]=='#')break;
cin
>>p
;
getnxt(p
);
cout
<<kmp(s
,p
)<<endl
;
}
return 0;
}
转载请注明原文地址:https://blackberry.8miu.com/read-35519.html