C++做题小技巧1:回文字符串(数)预处理(初步)

  • 时间:
  • 浏览:
  • 来源:互联网

回文字符串(数)预处理

当你遇到了一串很长的字符串,让你找出所有得回文数,你该如何做呢???

你可以分为以下两步骤:

  1. 长度为奇数:
    从头到尾枚举最中间的那个点,然后向两边扩展
  2. 长度为偶数
    从头到尾枚举中间的左边那个点,然后向两边扩展

具体操作可看代码:

#include<string>
#include<iostream>
using namespace std;
const int MAXN=1e5+4;
string s;
int isPa[MAXN][MAXN];/*记录字符串,此处不用
但是有些体重需要用到*/
int main(){
	int ans=0;
	cin>>s;
	int N=s.size();
	for(int i=0;i<N;i++)
	{
		int l=i,r=i;//l向左,r向右
		while(l>=0&&r<N&&S[l]==S[r])
			isPa[l--][r++]=1,ans++;//奇数
		l=i,r=i+1;
		while(l>=0&&r<N&&S[l]==S[r])
			isPa[l--][r++]=1,ans++;//偶数
	}
	printf("%d",ans);
}

此处复杂度为 O ( n l o g n ) O(nlog_n) O(nlogn)
notice:还有一种更高级的将在以后出现 复 杂 度 为 O ( n ) _{_{_{_{_{_{复杂度为O(n)}}}}}} O(n)
好了,本期文章就到这里了,咱们下期再见

传送门:未打开,还在挖掘中

本文链接http://www.dzjqx.cn/news/show-617574.html