表达式求值

//1930
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<unordered_map>
#include<stack>
using namespace std;
stack<int>num;
stack<char>op;
unordered_map<char,int>pr={{'+',1},{'-',1},{'*',2},{'/',2},{'^',3}};
int power(int a,int n){
if(a==1||n==0)return 1;
    int b=power(a,n/2);
    int ans=b*b;
    if(n%2==1)ans*=a;
    return ans;
}
bool  eval(){
    auto b=num.top();num.pop();
    auto a=num.top();num.pop();
    auto c=op.top();op.pop();
    int x=0;
    if(c=='+')x=a+b;
    else if(c=='-')x=a-b;
    else if(c=='*')x=a*b;
    else if(c=='^')x=power(a,b);
    else if(c=='/'){
       if(b) x=a/b;
        else{
         cout<<"INVALID"<<endl;
         return false;
        }
    }
    num.push(x);
    return true;
}
bool calculate(string str){
    while(!num.empty())num.pop();
    while(!op.empty()) op.pop();//注意清空
for(int i=0;i<str.size();i++){
        auto c=str[i];
        if(isdigit(c)){
            int x=0,j=i;
            while(j<str.size()&&isdigit(str[j]))
            x=x*10+str[j++]-'0';
            i=j-1;
            num.push(x);
        }
        else if(c=='(')    op.push(c);
        else if(c==')'){
            while(op.top()!='(')if(!eval())return false;
            op.pop();
        }
        else {
            while(op.size()&&op.top()!='('&&pr[op.top()]>=pr[c])if(!eval())return false;
            op.push(c);
        }
    }
    while(op.size())if(!eval())return false;
    cout<<num.top()<<endl;
    return true;
}
int main(){
    string str;
   while(cin>>str){
    if(!calculate(str))continue;
    }
    return 0;
}

括号匹配

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<unordered_map>
using namespace std;
unordered_map<char,int>p;
bool check(string str){
stack<char>n;
    for(auto c:str){
   if(c!='('&&c!=')'&&c!='{'&&c!='}'&&c!='['&&c!=']'&&c!='<'&&c!='>')continue;
        int t=p[c];//大于0为右括号
        if(t>0){
          if(n.empty()||n.top()!=-t)return false;
          n.pop();
        }
        else{
           if(n.size()&&abs(n.top())<=abs(t))return false;
            n.push(t);
        }
    }
    return n.empty();
}
int main(){
    p['{']=-4,p['}']=4;
    p['[']=-3,p[']']=3;
    p['(']=-2,p[')']=2;
    p['<']=-1,p['>']=1;
    int T;
    cin>>T;
    string str;
    while(T--){
     cin>>str;
        if(check(str))puts("Match");
        else puts("Fail");
    }
return 0;
}

KMP

识别连续字符串

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
const int N=100010;
int ne[N];int cnt;int k;
string repeatString(const string& str, int k) {
    string result;
    for (int i = 0; i < k; ++i) {
        result += str;
    }
    return result;
}
void buildnext(string s,int ne[],int m){
    int k=ne[0]=-1;
    for(int j=0;j<m;j++){
        while(k>=0&&s[k]!=s[j])
        {k=ne[k];}
        ne[j+1]=++k;
    }
}
int KMP(string s,string p,int n,int m){
    int i=0,j=0,cnt=0;
    buildnext(p,ne,m);
    while(i<n&&j<m){
    if(j==-1||s[i]==p[j])i++,j++;
    else j=ne[j];
    if(j==m){
        cnt++;
        j=ne[j];
    }
    }
    return cnt;
}
int main(){
    int m;string str;
    scanf("%d",&m);
    while(m--){
     cin>>str>>k;
     string result =repeatString("edgnb",k);
     int n=str.size(),p=result.size();
     printf("%d\n",KMP(str,result,n,p));
    }
    return 0;
}

第二短前后缀反转 第二长

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100010;
int ne[N];
string reverse(string str){
    int n=str.size();
    for(int i=0;i<n/2;i++){
            char temp=str[i];
            str[i]=str[n-i-1];
            str[n-i-1]=temp;
        }
        return str;
}
void buildnext(string s,int ne[],int m){
    memset(ne,0,sizeof ne);
    int k=ne[0]=-1;
    for(int j=0;j<m;j++){
        while(k>=0&&s[k]!=s[j])
        {k=ne[k];}
        ne[j+1]=++k;
    }
}
int main(){
    string str;
    int res1,res2;
    while(getline(cin,str)){
        res1=0,res2=0;
        string str2=reverse(str);
        int n=str.size();

        buildnext(str2,ne,n);
        for(int i=1;i<=n;i++)
        res1=max(res1,ne[i]);

        buildnext(str,ne,n);

        if(ne[ne[n]]>=0)
        res2=n-2*ne[ne[n]]>=0?n-2*ne[ne[n]]:0;

        else res2=n;

        printf("%d\n",res1+res2);
    }
    return 0;
}

最短前后缀

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000010;
int ne[N];
void buildnext(string s,int ne[],int m){
    int k=ne[0]=-1;
    for(int j=0;j<m;j++){
        while(k>=0&&s[k]!=s[j])
        {k=ne[k];}
        ne[j+1]=++k;
    }
}
//DP 思想
int main(){
    int n;string str;
    cin>>n>>str;
    buildnext(str,ne,n);
    long long ans=0;//初始化
    for(int i=1;i<=n;i++){
    if(!ne[i])continue;
    else if(ne[ne[i]]!=0)ne[i]=ne[ne[i]];
    }
    for(int i=1;i<=n;i++)
    if(ne[i]==0)ans+=0;
    else ans+=i-ne[i];
    cout<<ans<<endl;
return 0;
}