Pagini recente » *PAGINA LUI VI$$U* | Monitorul de evaluare | Transport | Cod sursa (job #1874764) | Cod sursa (job #1769980)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
ifstream F("strmatch.in");
ofstream G("strmatch.out");
const int N = 2000010;
int z[N*2],n,m;
char a[N*2];
int cans;
vector<int> ans;
void expand(int& l, int& r) {
while (a[r - l + 1 + 1] == a[r + 1] && r + 1 <= n) {
++r;
}
}
int main()
{
F>>(a+1);
m = strlen(a+1);
F>>(a+m+1);
n = strlen(a+1);
int l = 0 , r = 0;
for (int i = 2; i <= n ; ++i) {
if (i > r) {
if (a[i] == a[1]) {
l = r = i;
expand(l, r);
z[i] = r - l + 1;
}
} else {
if (i + z[i - l + 1] - 1 < r) {
z[i] = z[i - l + 1];
} else {
l = i;
expand(l, r);
z[i] = r - l + 1;
}
}
}
for (int i=m+1;i<=n;++i)
if ( z[i] >= m )
{
cans++;
if ( cans <= 1000 )
ans.push_back(i-m);
}
G<<cans<<'\n';
for (int i=0;i<int(ans.size());++i)
G<<ans[i]-1<<' ';
G<<'\n';
}