Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Profil TeamFIIA | Cod sursa (job #1010232) | Cod sursa (job #2201764)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000005], B[2000005];
int N, M, P[2000005],v[1005];
void prep()
{
int i, k = 0;
for(i = 1; i < M; i++)
{
if(A[i] == A[k]) k++;
else {
k = 0; if(A[i] == A[k]) k++;
}P[i] = k;
}
}
int main()
{
int i, k = 0, q = 0;
fin.getline(A,2000005); M = strlen(A);
fin.getline(B,2000005); N = strlen(B);
prep();
for(i = 0; i < N; i++)
{
if(A[k] == B[i]) k++;
else k = P[max(k - 1, 0)];
if(k == M)
{
v[0]++, v[min(v[0],1001)] = i - M + 1;
k = P[M - 1];
}
}
fout << v[0] << "\n";
for(i = 1; i <= min(v[0],1000); i++) fout << v[i] << " ";
return 0;
}