今天题目除了有思维难度以外没什么好说的（第五题一开始连题目意思都没读懂。。。）

1 Spelling Check{

1. 题意：给定两个长度相差为1的字符串，求最终字符串a是否能通过删除其中一个字符得到字符串b,如果能，输出每个可能的删除位置，如果不能，输出0

2. 思路：因为只要求删除一个字符，所以我们可以先算出这两个字符串中已经可以匹配的前缀和后缀，然后剩下的就是有可能出现不匹配的位置，枚举节点，只要前缀还能大于当前下标：l>=i。且后缀：r>=n-i-1.那么将这个节点的下标加1放入答案数组中

}

核心代码：

 while(l<m&&a[l]==b[l]) l++;//计算可匹配的前缀长度
    int r=0;
    while(r<m&&a[n-1-r]==b[m-1-r]) r++;//计算可匹配的后缀长度
    vector<int> ans;
    for(int i=0;i<n;i++){
        if(l>=i&&r>=n-i-1){//如果仍满足
             ans.push_back(i+1);
        }
    }

2 Prefix--suffix Palindrome{
1.题意：给你一个字符串，要求你找出其中的某一个字符串，我们规定你找出的最长字符串必须满足一下三个定义：

       1 长度必须不能超过原串。

       2 必须是回文串

       3 是由原串中的前缀和后缀拼接而来

      输出这个字符串

3. 思路：这题首先要能够找到最长的由前缀和后缀拼接而来的字符串，就要先找到最长的回文前缀和后缀。这里我选择用next数组来求最长回文前后缀（本人认为其实并不难想，可能是更熟悉KMP吧，所以就没想用哈希），除中间不能匹配的以外，其余的在加上最长回文前缀和最长公共后缀之间取到最大长度。因为有了next数组，所以查询最长回文前后缀的时间复杂度接近O(1)

}

核心代码：

首先是这题next 数组的计算：

vector<int> pf(string s){//与正常模版稍微有点不一样
            int n=s.size();
            vector<int> p(n,0);//next数组
          for(int i=1;i<n;i++){
            int j=p[i-1];
            while(j>0&&s[j]!=s[i]) j=p[j-1];//这里如果匹配不了必须跳回来再找
            if(s[i]==s[j]) j++;
            p[i]=j;
          }
          return p;
}

再是合法字符串的计算：

string solve(string s){
       int n=s.size();
       int l=0,r=n-1;
       while(l<r&&s[l]==s[r]){
        l++; r--;
       }
       if(l>=r) return s;//全部匹配，直接返回原串
       string mid=s.substr(l,r-l+1);
       string res=mid;
       reverse(res.begin(),res.end());
       string t1=mid+res;
       vector<int> p1=pf(t1);
       int len1=p1.back();//最长回文前缀
       string t2=res+mid;
       vector<int> p2=pf(t2);
       int len2=p2.back();//最长回文后缀
       string p=s.substr(0,l);
       string h=s.substr(r+1);
       if(len1>=len2) return p+mid.substr(0,len1)+h;
       else return p+mid.substr(mid.size()-len2)+h;
}

3 Palindrome Pairs(坑题){
  1.题意：给定n个字符串，现在问这n个字符串之间是否能互相连接并重组形成回文串，求出最多产生的回文串数量

2. 思路:我们假设一个回文串ababa和一个回文串totot,不难发现这两个字符串中出现次数为奇数次的字母不超过一个，因此我们要想得到一个回文串，就得先需要保证两个字符串之间的字母出现次数尽量为偶数或为奇数的字母为1，因此对于这26个字母，我们可以将其出现次数压缩为：mask^=(1<<(s[i]):“mask表示当前位置的状态，异或s[i]表示对其 取反，如果最终这一位剩下的数为1则说明是奇数，0则说明是偶数，对于每一个串，我们希望最终的结果mask恒为0或有一位为1.。”

接着就是查询贡献：初始化一个unordered_map(注意：这里必须是unordered_map！因为无序容器中对数值的查询为O(1)复杂度，而有序map的复杂度为O(logn),仅是这里就可能导致超时)，然后加上0到26内配对后每个字母的偶数次，并更新哈希表cnt[mask]++;

3. 算法：哈希hashing,异或位运算

}

核心代码：

  for(char c:s){
            mask^=(1<<(c-'a'));//判断奇偶性
        }
        ans+=cnt[mask];//如果是偶数个
        for(int j=0;j<26;j++){
            int t=mask^(1<<j);//为奇数时答案为2的幂
            ans+=cnt[t];
        }
        cnt[mask]++;
       }

    4 Erase and Extend(水题){

1. 题意：给定一个字符串的长度n和字符串以及我们需要得到的新字符串的长度k，并规定：新字符串可以由原字符串删去最后一个字符或直接复制原串得来，求最终字典序最小的字符串并输出

2. 思路：因为这题只要求我们求一个满足长度为k且字典序最小的字符串，所以我们只需要在扫描原字符串时判断改位是否还是小于前面出现的字符，如果不是了直接退出，如果还是则更新可复制的长度

}

完整代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    string p;
    cin>>p;
    int s=1;//最优前缀长度
    for(int i=1;i<n;i++){
        if(p[i]>p[i%s]) break;//不优了退出
        if(p[i]<p[i%s]) s=i+1;//继续更新
    }
   for(int i=0;i<k;i++) cout<<p[i%s];
}

5 Fixed prefix permutations{
1.题意：有一组数组，我们规定其美丽值为下标i的值为i能走的最大长度k。现在规定一个新的数组r，其第j项的值为两个数组的值q[p[j]]，

求最终r能得到的美丽值的最大值

3. 思路：（一开始时没读懂题意。。。）对于r数组中的每一项的值，其公式为：p[i]*q[j]=p[q[j]]。如果一个一个去枚举i,j其时间复杂度为O(n^2*m),十分的不划算。但是我们如果假设一个数组inv,inv[l]表示一个值l在原数组中出现的次数，那么原来的题目意思其实就从要用两个数组的乘积去求值变成了在所有inv数组里求最大公共前缀。所以我们只需要用集合维护前缀的十进制掩码值，并在最后查询如果有出现这个l,输出当前下标

3.算法：集合

}

AC代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        int n,m;
        cin >> n >> m;
        vector<vector<int>> out(n+1,vector<int>(m+1));
        vector<vector<int>> oin(n+1,vector<int>(m+1));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>out[i][j];
                oin[i][out[i][j]]=j;//r数组中的元素排列
            }
        }
        unordered_set<long long> st;
        for(int i=1;i<=n;i++){
            long long code=0;
            for(int j=1;j<=m;j++){
                code=code*10+oin[i][j];
                st.insert(code);
            }
        }
        for(int i=1;i<=n;i++){
           int ans=0;
           long long code=0;
            for(int j=1;j<=m;j++){
                code=code*10+out[i][j];
                if(st.count(code)){
                    ans=j;
                }
                else break;
            }
            cout<<ans<<' ';
        }
       cout<<endl;
    }
}

6 Sasha and one more name{

1. 题意：有一个回文字符串，你现在可以对其进行分割，分割而成的子串之间可以相互交换位置，求最终能否经过k次切割后得到一个与原串不同的新字符串，如果能，输出最小的k,不能则输出Impossible

2. 思路：我们需要证明一下是否所有的回文字符串都能经过不多于2次的分割机会得到一个全新的回文字符串。首先判断Impossible的情况（这里可能是题目数据水，我只判断了一个如果全部字符都相等都过了），如果是全部字符都相等或者除了中间一个字符以外的所有字符都相等，那么原串不可能再分割成一个全新回文字符串，输出Impossible。然后就是有解的情况：首先如果是一个回文字符串，那么其全新回文字符串一定是通过只在中间切一刀或者在除了中间相等部分以外的地方各切两刀得到。所以我们可以不断迭代新的字符串t=s.substr(0,i)+s.substr(i)，然后如果此时的新字符串如果是回文串直接输出1，如果不是输出2，印证了我们非1即2的想法

}

先是判断回文：

bool ispalindrome(string s){
    int l=0,r=s.size()-1;
    while(l<r&&s[l]==s[r]){//如果能匹配那么一直缩小范围
        l++;
        r--;
    }
    if(l<r) return false;//没法实现碰撞那么不是
    else return true;
}

然后是迭代枚举：

for(int i=0;i<s.size();i++){
        string t=s.substr(i)+s.substr(0,i);
        if(t!=s&&ispalindrome(t)){
            cout<<1;//是1非2
            return 0;
        }
    }
    cout<<2;//1不行那就输出2