[ABC324C] Error Correction
作者:
多米尼克領主的致意
,
2024-04-26 17:02:01
,
所有人可见
,
阅读 2
字符串基础 O(n)
第一次用了substr()函数 复杂度变成O(n^2)TLE
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n;
string ans;
string s;
bool isg[N];
int cnt;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> ans;
// for(int i = 1;i <= n;i++)
// {
// cin >> s[i];
// }
for(int i = 1;i <= n;i++)
{
cin >> s;
string x, y;
int ls = s.size(), lt = ans.size();
if(abs(ls - lt) >= 2)continue;
if(ls == lt)//#1
{
if(s == ans)
{
cnt++;
isg[i] = true;
continue;
}
int k;
for(int j = 0;j < ls;j++)//#4
{
if(s[j] != ans[j])
{
k = j;
break;
}
}
string one = "", two = "";
for(int j = 0;j < k;j++)
{
one += s[j];
two += ans[j];
}
for(int j = k + 1;j < ls;j++)
{
one += s[j];
two += ans[j];
}
if(one == two)
{
cnt++;
isg[i] = true;
continue;
}
}
else{
if(ls > lt)//#3
{
int k = ls - 1;
for(int j = 0;j < lt;j++)
{
if(s[j] != ans[j])
{
k = j;
break;
}
}
string end = "";
for(int j = 0;j < k;j++)end += s[j];
for(int j = k + 1;j < ls;j++)end += s[j];
if(end == ans)
{
cnt++;
isg[i] = true;
continue;
}
}
else{//#2
int k = lt - 1;
for(int j = 0;j < ls;j++)
{
if(ans[j] != s[j])
{
k = j;
break;
}
// cout << k << endl;
}
string end = "";
for(int j = 0;j < k;j++)end += ans[j];
for(int j = k + 1;j < lt;j++)end += ans[j];
if(end == s)
{
cnt++;
isg[i] = true;
continue;
}
}
}
}
cout << cnt << endl;
for(int i = 1;i <= n;i++)
{
if(isg[i])cout << i << " ";
}
return 0;
}