前言
时隔两年再一次登上账号 本菜鸡尝试回归捏
复习了kmp和st表 发现自己没有发过博客
代码
#include<iostream> #include<cstring> using namespace std; int kmp[10000001]; char s1[10000001],s2[10000001]; int main() { cin>>s1+1>>s2+1; int len1=strlen(s1+1),len2=strlen(s2+1); int j=0; for (int i=2;i<=len2;i++) //先自身匹配构建kmp数组 { while (j&&j<=len2&&s2[i]!=s2[j+1]) j=kmp[j]; if (s2[i]==s2[j+1]) j++; kmp[i]=j; } j=0; for (int i=1;i<=len1;i++) //用模式串与文本串匹配 { while (j&&j<=len2&&s1[i]!=s2[j+1]) j=kmp[j]; if (s1[i]==s2[j+1]) j++; if (j==len2) { cout<<i-len2+1<<endl; j=kmp[j]; } } for (int i=1;i<=len2;i++) cout<<kmp[i]<<" "; }
#include<iostream> #include<cmath> #include<cstdlib> using namespace std; int n,m; int maxx[1000001][21]; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } void st() //构建倍增查找数组 { for (int j=1;j<=21;j++) for (int i=1;(i+(1<<j))-1<=n;i++) maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1]); //将其拆成两半 递推得到最大值 } int quire(int l,int r) //将其拆分为左右两边,即使有重复也不影响其贡献 { int k=log2(r-l+1); return max(maxx[l][k],maxx[r-(1<<k)+1][k]); } int main () { cin>>n>>m; for (int i=1;i<=n;i++) maxx[i][0]=read(); st(); for (int i=1,x,y;i<=m;i++) { x=read(); y=read(); printf("%d\n",quire(x,y)); } }
标签:10000001,ch,int,s2,st,kmp,include From: https://www.cnblogs.com/zjzjzj/p/16708441.html