NC13590. 永远的零
描述
输入描述
多组输入，每行为一串数，每个数字在0到9之间。保证这串数的第一个数字非0。数字个数n满足2≤n≤10^6。 所有输入数字个数不超过4×10^6。
输出描述
对每组数据输出一行，即算出来的数后面最多有多少个0。
示例1
输入:
2017 2018
输出:
0 1
C++(g++ 7.5.0) 解法, 执行用时: 50ms, 内存消耗: 13844K, 提交时间: 2023-04-17 13:05:37
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1000002
char s[MAXN],str[MAXN];
int fail[MAXN];
int num9[MAXN];
int len,zero;
void make_fail()
{
for(int i=1,j=0;s[i];i++)
{
while(j&&s[i]!=s[j]) j=fail[j-1];
if(s[i]==s[j]) fail[i]=++j;
else fail[i]=0;
}
}
int search(char *str)
{
int ans=0;
for(int i=len,j=0;i>=0;i--)
num9[i]=str[i]=='9'?++j:j=0;
for(int i=1,j=0;i<=len;i++)
{
for(;j&&str[i]!=s[j];j=fail[j-1])
{
if(i-j>j) ans=max(ans,i==len?min(j+num9[j],i-j):j);
else if(j>=zero) ans=max(ans,i-j+num9[2*(i-j)]);
}
if(str[i]==s[j]) j++;
}
return max(ans,zero-1);
}
int main()
{
while(scanf("%s",str)==1)
{
len=strlen(str);
reverse(str,str+len);
for(zero=0;str[zero]=='0';s[zero++]='0');
s[zero]='9'+'1'-str[zero];
for(int i=zero+1;i<len;i++)
s[i]='9'+'0'-str[i];
s[len]=0;
make_fail();
printf("%d\n",search(str));
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 55ms, 内存消耗: 9972K, 提交时间: 2020-04-15 21:22:45
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1000002
char s[MAXN],str[MAXN];
int fail[MAXN];
int num9[MAXN];
int len,zero;
void il(){
for(int i=1,j=0;s[i];i++){
while(j&&s[i]!=s[j]) j=fail[j-1];
if(s[i]==s[j]) fail[i]=++j;
else fail[i]=0;
}
}
int search(char *str){
int ans=0;
for(int i=len,j=0;i>=0;i--)
num9[i]=str[i]=='9'?++j:j=0;
for(int i=1,j=0;i<=len;i++){
for(;j&&str[i]!=s[j];j=fail[j-1]){
if(i-j>j) ans=max(ans,i==len?min(j+num9[j],i-j):j);
else if(j>=zero) ans=max(ans,i-j+num9[2*(i-j)]);
}
if(str[i]==s[j]) j++;
}
return max(ans,zero-1);
}
int main(){
while(scanf("%s",str)==1){
len=strlen(str);
reverse(str,str+len);
for(zero=0;str[zero]=='0';s[zero++]='0');
s[zero]='9'+'1'-str[zero];
for(int i=zero+1;i<len;i++)
s[i]='9'+'0'-str[i];
s[len]=0;
il();
printf("%d\n",search(str));
}
}
C++11(clang++ 3.9) 解法, 执行用时: 62ms, 内存消耗: 13900K, 提交时间: 2020-03-10 11:12:46
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1000002
char s[MAXN],str[MAXN];
int fail[MAXN];
int num9[MAXN];
int len,zero;
void make_fail()
{
for(int i=1,j=0;s[i];i++)
{
while(j&&s[i]!=s[j]) j=fail[j-1];
if(s[i]==s[j]) fail[i]=++j;
else fail[i]=0;
}
}
int search(char *str)
{
int ans=0;
for(int i=len,j=0;i>=0;i--)
num9[i]=str[i]=='9'?++j:j=0;
for(int i=1,j=0;i<=len;i++)
{
for(;j&&str[i]!=s[j];j=fail[j-1])
{
if(i-j>j) ans=max(ans,i==len?min(j+num9[j],i-j):j);
else if(j>=zero) ans=max(ans,i-j+num9[2*(i-j)]);
}
if(str[i]==s[j]) j++;
}
return max(ans,zero-1);
}
int main()
{
while(scanf("%s",str)==1)
{
len=strlen(str);
reverse(str,str+len);
for(zero=0;str[zero]=='0';s[zero++]='0');
s[zero]='9'+'1'-str[zero];
for(int i=zero+1;i<len;i++)
s[i]='9'+'0'-str[i];
s[len]=0;
make_fail();
printf("%d\n",search(str));
}
return 0;
}