Pagini recente » Cod sursa (job #2941843) | Cod sursa (job #1719300) | Cod sursa (job #2866804) | Cod sursa (job #1086431) | Cod sursa (job #1628009)
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<queue>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
const int N = 201000;
struct str {
long long nr;
char c;
};
int n, m;
str a[2 * N], b[N], l[N];
vector<int> poz;
bool cmp(str a, str b) {
return (a.nr == b.nr && a.c == b.c);
}
int z[2 * N];
void calcpot() {
int i, j;
for(i = 1; i <= n; ++i)
l[i] = a[i];
int nr = 0;
for(i = 1; i <= n; ++i) {
a[++nr] = l[i];
}
for(i = 1; i <= m; ++i)
a[++nr] = b[i];
int el, pmax = 0;
for(i = 2; i <= nr; ++i) {
if(i >= pmax) {
for(j = i; cmp(a[j], a[j - i + 1]) && j <= nr; ++j);
--j;
z[i] = j - i + 1;
pmax = j;
el = i;
}
else {
z[i] = min(z[i - el + 1], pmax - i + 1);
for(j = i + z[i] - 1; cmp(a[j], a[j - i + 1]) && j <= nr; ++j);
--j;
z[i] = j - i + 1;
if(j > pmax) {
pmax = j;
el = i;
}
}
if(i > n && z[i] >= n) {
poz.push_back(i - (n));
}
}
}
void calc() {
int i, j;
calcpot();
int r = 0;
cout << poz.size() << "\n";
for(i = 0; i < poz.size(); ++i)
cout << poz[i] - 1 << " ";
}
char s1[N], s2[N];
int main() {
int i, j;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> s1;
cin >> s2;
n = strlen(s1);
m = strlen(s2);
for(i = 1; i <= n; ++i) {
a[i].c = s1[i - 1];
}
for(i = 1; i <= m; ++i) {
b[i].c = s2[i - 1];
}
/*
cin >> m >> n;
for(i = 1; i <= m; ++i) {
scanf("%I64d-%c ", &b[i].nr, &b[i].c);
if(i > 1 && b[i].c == b[i - 1].c) {
b[i - 1].nr += b[i].nr;
--m;
--i;
}
}
for(i = 1; i <= n; ++i) {
scanf("%I64d-%c ", &a[i].nr, &a[i].c);
if(i > 1 && a[i].c == a[i - 1].c) {
a[i - 1].nr += a[i].nr;
--n;
--i;
}
}
if(n == 1) {
int r = 0;
for(i = 1; i <= m; ++i) {
if(a[1].c == b[i].c)
r += max(0LL, b[i].nr - a[1].nr + 1);
}
cout << r;
return 0;
}
if(n == 2) {
if(m == 1) {
cout << 0;
return 0;
}
int r = 0;
for(i = 1; i < m; ++i) {
if(a[1].c == b[i].c && a[2].c == b[i + 1].c && a[1].nr <= b[i].nr && a[2].nr <= b[i + 1].nr)
++r;
}
cout << r;
return 0;
}
if(m < n) {
cout << 0;
return 0;
}
*/
calc();
return 0;
}