Pagini recente » Profil M@2Te4i | Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1771389)
#include <bits/stdc++.h>
#define NMax 2000003
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[2*NMax];
int kmp[2*NMax];
int S,L,ans;
vector<int> A;
int main()
{
f.getline(s,2*NMax);
S = strlen(s);
L = S;
s[S] = '#';
f.getline(s + S + 1,2*NMax);
S = strlen(s);
kmp[0] = 0;
for(int i = 1; i < S; ++i){
int j = kmp[i - 1];
while(j > 0 && s[i] != s[j])
j = kmp[j - 1];
if(s[i] == s[j])
kmp[i] = j + 1;
if(kmp[i] == L && ans < 1000){
ans++;
A.push_back(i - L - L);
}
}
g << A.size() << '\n';
for(int i = 0; i < A.size(); ++i){
g << A[i] << ' ';
}
return 0;
}