**t1 **：比较两个字符串，从左到右找到第一个不同的位置。删除该位置后若剩余字符完全相同，则该位置可行。因为第一个字符串总比第二个多一个字符，所以只需检查每个可能删除的位置，看删除后是否与第二个字符串相等。输出可行位置总数及所有位置编号，若无可行方案则输出0。

#include<bits/stdc++.h>
using namespace std;
char s1[1000010],s2[1000010];
int len1,len2;
int an;
int main(){
	scanf("%s",s1+1);len1=strlen(s1+1);
	scanf("%s",s2+1);len2=strlen(s2+1);
	int t=1,bj=0,ans=0;
	for(int i=1;i<=len1;i++){
		if(s1[i]==s2[t]){
			t++;
		}else{
			an=i;
			bj++;
		}
	}
	if(bj>1){
		printf("0");
		return 0;
	}
	for(int i=an-1;i>=1;i--){
		if(s1[i]==s1[an]){
			ans++;
		}
		else break;
	}
	printf("%d\n",ans+1);
	for(int i=an-ans;i<=an;i++) printf("%d ",i);
	return 0;
}

**t2 **：从字符串两端同时向中间推进，匹配相同的字符，直到遇到不相等的字符。匹配好的部分作为答案的前缀和后缀。剩余中间部分找出最长回文子串作为中心。将前缀、中心、后缀拼接起来即为最长满足条件的回文串。若两端完全匹配，则整个字符串就是答案。

#include<bits/stdc++.h>
using namespace std;
bool huiwen(string s){
	int i=0,j=s.size()-1;
	while(i<j){
		if(s[i]!=s[j]) return 0;
		i++;j--;
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--){
		string s;
		cin>>s;
		int n=s.size();
		int i=0,j=n-1;
		while(i<j&&s[i]==s[j]){
			i++;
			j--;
		}
		if(i>=j){
			cout<<s<<"\n";
			continue;
		}
		string a=s.substr(0,i);
		string b=s.substr(j+1);
		string m=s.substr(i,j-i+1);
		string ans="";
		for(int len=1;len<=m.size();len++){
			string t=m.substr(0,len);
			if(huiwen(t)&&t.size()>ans.size()){
				ans=t;
			}
		}
		for(int len=1;len<=m.size();len++){
			string t=m.substr(m.size()-len);
			if(huiwen(t)&&t.size()>ans.size()){
				ans=t;
			}
		}
		cout<<a+ans+b<<"\n";
	}
	return 0;
}

**t3 **：两个字符串拼接后能重排成回文串，当且仅当两者的奇偶字符状态合在一起后奇数字符数不超过1。将每个字符串的奇偶状态压缩成26位二进制掩码，统计每种掩码出现次数。对每个串，找与它配对的掩码（相同或只差一位），累加计数后除以2去重。

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin>>N;
	unordered_map<int,int> cnt;
	vector<int> masks(N);
	for(int i=0;i<N;i++){
		string s;
		cin>>s;
		int mask=0;
		for(char c:s){
			mask^=(1<<(c-'a'));
		}
		masks[i]=mask;
		cnt[mask]++;
	}
	long long ans=0;
	for(int i=0;i<N;i++){
		int mask=masks[i];
		cnt[mask]--;
		ans+=cnt[mask];
		for(int k=0;k<26;k++){
			int gt=mask^(1<<k);
			ans+=cnt[gt];
		}
		cnt[mask]++;
	}
	cout<<ans/2<<"\n";
	return 0;
}

**t4 **：考虑原字符串的所有前缀，取其中字典序最小的前缀作为复制单元。因为删除尾部字符可以任选前缀，复制该前缀能得到最小结果。枚举每个前缀，不断复制直到长度达到k，截断到恰好k位，取所有结果中字典序最小的字符串。

#include <bits/stdc++.h>
using namespace std;
int n,k;
string s,ans,s1;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ans=string(5000,'z');
	cin>>n>>k>>s;
	for(int i=1;i<=(int)s.size();i++){
		s1=s.substr(0,i);
		while((int)s1.size()<k){
			s1=s1+s1;
		}
		ans=min(ans,s1.substr(0,k));
	}
	cout<<ans;
	return 0;
}

**t5 **：对每个排列a_i，它和某个a_j的乘积美丽值为k，意味着对于前k个位置，a_j在a_i中值为pos的位置上恰好等于pos。由于m≤10，可以直接对每个i枚举所有j，检查美丽值并取最大值。n总和5e4，复杂度可接受。

#include<bits/stdc++.h>
using namespace std;
int T,n,m,p[20],a[50050][20];
int main(){
    scanf("%d",&T);
    while(T--){
        set<vector<int>> st[20];
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&a[i][j]);
                p[a[i][j]]=j;
            }
            for(int j=1;j<=m;j++){
                vector<int> v;
                for(int k=1;k<=j;k++) v.push_back(p[k]);
                st[j].insert(v);
            }
        }
        for(int i=1;i<=n;i++){
            int ans=0;
            for(int j=m;j>=1;j--){
                vector<int> v;
                for(int k=1;k<=j;k++) v.push_back(a[i][k]);
                if(st[j].count(v)){
                    ans=j;
                    break;
                }
            }
            printf("%d ",ans);
        }
        printf("\n");
    }
    return 0;
}

**t6 **：若原串所有字符相同则无解。若字符串长度为偶数且前后两半不同，切1刀交换两半即可得到不同回文串。否则尝试切2刀，将三段重排后检查是否为不同回文串。若存在则答案为2，否则Impossible。n≤5000，枚举切割位置即可

#include<bits/stdc++.h>
using namespace std;
bool isPal(string s){
	int l=0,r=s.size()-1;
	while(l<r){
		if(s[l]!=s[r]) return 0;
		l++;r--;
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	int n=s.size();
	bool flag=1;
	for(int i=1;i<n;i++){
		if(s[i]!=s[0]){
			flag=0;
			break;
		}
	}
	if(flag){
		cout<<"Impossible\n";
		return 0;
	}
	for(int i=1;i<n;i++){
		string t=s.substr(i)+s.substr(0,i);
		if(isPal(t)&&t!=s){
			cout<<1<<"\n";
			return 0;
		}
	}
	cout<<2<<"\n";
	return 0;
}