前言

持续记录OJ算法
 
pipioj

字符串

序列自动机

 
题目id：1343 ， 1039
 
 
KMP
 

char s[N],t[N];
int Next[N],n,m;
void getNext(){
    int j=0,k=-1; ///初始时,next[0]=-1,用 k 保存 next[j]
    Next[j]=-1;
    while(j<m-1){ ///注意是根据第 j 位求 j+1 位，所以 j=m-2 时就能求出 m-1 的值了，然后结束循环
        if(k==-1||t[j]==t[k])Next[++j]=++k; /// 第 二 种 情 况 t[j]=t[k] 时 ,满 足 下 一 位next[j+1]的定义
        else k=Next[k]; ///第三种情况 根据前后两端完全相同的信息 在前一段[0~next[k]]找满足第二种情况的位置 k
     } 
}

int kmp(){
 getNext(); ///求 next 数组
 int i=0,j=0,ans=0;
 while(i<n){
    if(j==-1||s[i]==t[j]){ ///如果当前位匹配 则都++
        if(j+1==m){ ///如果 j 已经匹配满了 说明找到了一个答案
           //执行相关操作
        }
        else{ ///正常操作 i++ j++
            ++i;++j;
        }
    }
    else j=Next[j]; ///失配的情况
    }
 return ans;
}

 
 
例题：1344
 
 
字符串HASH
 
顾名思义，就是将不同字符串映射成不同数字。
单独地把一个串映射成数字而不能获得这个子串的信息，这种映射是低端的。
如果能够将一个字符串HASH的同时方便的调取子串的HASH值，那么很多操作将十分方便。

 
题目举例：判断回文串（1345）
要判断S[L ~ R]是否为回文串，只需判断S[L ~ R]的HASH值是否与S[R~L]的HASH值相等。
 
 

数学专题

 
 
欧氏距离
 
 
同余定理
 
给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。
 
在算法题中应用场景： 比如我们要计算A%B，但是A非常大，我们就不能再简单的直接使用A%B，这样会内存超限---->在这种情况下我们就必须使用同余定理。
 
举例：假设A=22345
 

int ans = 0;
ans = (ans*10+2)%p;
ans = (ans*10+2)%p;
ans = (ans*10+3)%p;
ans = (ans*10+4)%p;
ans = (ans*10+5)%p;
//最终得到的ans值便 等同于 22345%p

 
例题：1103
 
 
中位数定理
 
现在已知数轴上有 n 个点 x1,x2 … xn，如何找到一个点x，使得|x-x1|+|x-x2|+…+|x-xn|的值最小?
 
答案: 这个点x就是这些数中的中位数
 
例题：1018
 
 
筛法--因子求和
 
打表法记录数字的因子之和，利用空间换时间

数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6.
 
假设想求数字的因子和
 

int q[N];
q[1]=1;  //1的因子是1 
for(int i=1;i<N;i++)  //枚举因子 
	for(int j=i+i;j<N;j+=i) //枚举拥有该因子的数字（自身除外） 
		q[j]+=i;

例题：1044
 
 
筛法--质数素数

const int N = 1e6+5;
bool p[N]; //0代表质数，1代表合数
int q[N];  //质数数组
void init()
{
	int id=0;
	p[1] = true;
	for(int i=2;i<N;i++) //枚举因子
	  if(!p[i])  //如果是质数
	  {
	  	q[id++]=i;  //添加进数组
	  	for(int j=i+i;j<N;j+=i)p[j]=true; //它的倍数的数全都是合数
	  }
}

 
例题：1053
 
 
二分法

记得控制精度

例题：1109

DFS与暴力专题

 
DFS这块没什么值得记录的，重在理解与多做题目。
 
 
暴力
 
题目：最长公共子序列1084

记录这一题是因为真滴难！
 
分析问题：
 
给你n个环，要你求出n个环的最长公共子序列。题目意思非常直白且不可做。好像之前学过的知识都失效了，根本没办法解决这个任务。看一眼数据范围，n<=10，环的长度小于8，这么小的数据范围，指数级别的暴力就登场了。
 
首先我们来看看二进制和子序列的关系。有一个长度为3的字符串”abc”，它的所有子序列为”a”,”b”,”c”,”ab”,”ac”,”bc”,”abc”考虑二进制001,010,011,100,101,110,111。发现了什么规律吗？
 

 
也就是说从001₁₁₁₍₁7的二进制)完美的表示出了abc的所有子序列。那么要枚举出长度为n的字符串的所有子序列，只需要for(int i=1;i<2^n;i++)对于i这个数字的二进制表示，为0的位置不取，为1的位置取。那么现在就解决了枚举子序列的问题。如何保证公共呢？用我们很熟悉的map<string,bool>mp即可，我们对一个个环来提取子序列，只有之前的环出现过的子序列，才是能保证公共，才是合法的。那么之前是否出现过直接mp.count()即可。具体细节，我们在代码里面体现。
 

• 个人理解：利用二进制来表示子序列，如果字符串长度为len，那么就是从1~2^len-1（代表二进制数的大小）取遍所有子序列。接下来判断这个子序列有没有出现过，出现过的便是公共序列。
   

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,bool>legal,mp;//legal代表合法序列，mp代表当前序列
unordered_map<string,bool>::iterator it;
string ans;  //最终输出的公共子串
int main()
{
	int n;
	string s;
	while(scanf("%d",&n)!=EOF)
	{
	  ans.clear();
	  for(int i=0;i<n;i++)
	  {
	  	cin>>s;
	  	string ts;
	  	mp.clear();
	  	int len = s.size(),tp=(1<<len);  //tp：2^len
	  	s+=s;   //将字符串s视作一个环
	  	for(int l=0;l<len;l++)//枚举起点
		{
		  for(int j=1;j<tp;j++)//枚举1~2^len-1之间的所有二进制数
		  {
		    for(int k=0;k<len;k++)//扫描二进制上的每一位
			  if(j&(1<<k))ts.push_back(s[l+k]); //将这个二进制数对应的字符串序列放进ts
			if(i==0||legal.count(ts)==1)mp[ts]=1;  
			ts.clear();
		  } 
		}
		if(i==n-1) //如果访问到了最后一个字符串
		{
		 for(it=mp.begin();it!=mp.end();it++)
		 {
             //有最长串便寻找最长串，如果长度相同便寻找字典序最小的串
		 	if(ans.size()<it->first.size())ans=it->first;
		 	else if(ans.size()==it->first.size()&&ans>it->first)ans=it->first;
		 }
		}
		else{
            //更新合法序列
            //比如legal中的合法序列在当前字符串中的子序列中并没有出现，那么它就不再是公共序列了，所以需要删除更新
			legal.clear();
			for(it=mp.begin();it!=mp.end();it++)legal[it->first]=1;
		} 
	  }
	  if(ans.size())cout<<ans<<endl;
	  else printf("0\n");
	}
	return 0;
}