首页 > 代码库 > Codeforces 39J Spelling Check hash
Codeforces 39J Spelling Check hash
题目链接:点击打开链接
题意:
给定2个字符串
选择第一个字符串的其中一个字母删除,使得2个字符串完全相同
问哪些位置可以选
思路:
hash求前缀后缀,然后枚举位置
#include <cstdio> #include <algorithm> #include<iostream> #include<string.h> #include <math.h> #include<queue> #include<map> #include<vector> #include<set> using namespace std; #define mod 100000007 #define ll long long #define N 1000050 char s[N], c[N]; vector <int> ans; ll l1[N], r1[N], l2[N], r2[N]; int main(){ int i, j; while(~scanf("%s",s+1)){ scanf("%s",c+1); int len1 = strlen(s+1), len2 = strlen(c+1); if(len1 -1 != len2){puts("0");continue;} l1[0] = 0; for(i = 1; i <= len1; i++) { l1[i] = l1[i-1]*26 + s[i]; if(l1[i]>=mod) l1[i] %= mod; } r1[len1+1] = 0; for(i = len1; i ; i--) { r1[i] = r1[i+1]*26 + s[i]; if(r1[i]>=mod) r1[i] %= mod; } l2[0] = 0; for(i = 1; i <= len2; i++) { l2[i] = l2[i-1]*26 + c[i]; if(l2[i]>=mod) l2[i] %= mod; } r2[len2+1] = 0; for(i = len2; i ; i--) { r2[i] = r2[i+1]*26 + c[i]; if(r2[i]>=mod) r2[i] %= mod; } ans.clear(); for(i = 1; i <= len1; i++) { ll a = l1[i-1] + r1[i+1]; ll b = l2[i-1]+r2[i]; if(a==b)ans.push_back(i); } cout<<ans.size()<<endl; for(i = 0; i <ans.size(); i++) printf("%d%c", ans[i], i==ans.size()-1?'\n':' '); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。