#433658 (C++14) No.599 回文かい

• 問題: No.599 回文かい
• ユーザー: kotatsugame
• 提出日時: 2020-02-23 04:18:42
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 237 ms / 4,000 ms
• コード長: 756 bytes
• コンパイル時間: 820 ms
• コンパイル使用メモリ: 71,260 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-10-10 01:30:36
• 合計ジャッジ時間: 2,371 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,820 KB
testcase_02	AC	2 ms; 6,820 KB
testcase_03	AC	2 ms; 6,820 KB
testcase_04	AC	3 ms; 6,820 KB
testcase_05	AC	2 ms; 6,820 KB
testcase_06	AC	2 ms; 6,816 KB
testcase_07	AC	2 ms; 6,820 KB
testcase_08	AC	2 ms; 6,816 KB
testcase_09	AC	2 ms; 6,816 KB
testcase_10	AC	34 ms; 6,820 KB
testcase_11	AC	22 ms; 6,820 KB
testcase_12	AC	37 ms; 6,816 KB
testcase_13	AC	23 ms; 6,820 KB
testcase_14	AC	63 ms; 6,816 KB
testcase_15	AC	67 ms; 6,816 KB
testcase_16	AC	208 ms; 6,816 KB
testcase_17	AC	237 ms; 6,816 KB
testcase_18	AC	2 ms; 6,816 KB
testcase_19	AC	2 ms; 6,816 KB
testcase_20	AC	2 ms; 6,816 KB
evil_0.txt	AC	48 ms; 6,816 KB

コンパイルメッセージ

main.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main()
      | ^~~~

ソースコード

#include<iostream>
#include<vector>
using namespace std;
//Longest Common Prefix(s,s.substr(i)) O(|s|)
#include<vector>
vector<int>Zalgo(const string&s)
{
	vector<int>ret(s.size());
	if(s.empty())return ret;
	ret[0]=s.size();
	int i=1,j=0;
	while(i<s.size())
	{
		while(i+j<s.size()&&s[j]==s[i+j])j++;
		ret[i]=j;
		if(j==0)
		{
			i++;
			continue;
		}
		int k=1;
		while(i+k<s.size()&&k+ret[k]<j)ret[i+k]=ret[k],k++;
		i+=k;j-=k;
	}
	return ret;
}
long mod=1e9+7,dp[10101];
string s;
main()
{
	cin>>s;
	dp[0]=1;
	long ans=0;
	for(int i=0;i*2<=s.size();i++)
	{
		ans+=dp[i];
		string t=s.substr(i,s.size()-i*2);
		vector<int>az=Zalgo(t);
		for(int j=1;2*j<=az.size();j++)
		{
			if(az[az.size()-j]>=j)(dp[i+j]+=dp[i])%=mod;
		}
	}
	cout<<ans%mod<<endl;
}