Pagini recente » Clasament igorj_6 | Cod sursa (job #537031) | Cod sursa (job #1630736) | Cod sursa (job #1587280) | Cod sursa (job #1781590)
//
// main.cpp
// KMP
//
// Created by Albastroiu Radu on 10/16/16.
// Copyright © 2016 Albastroiu Radu. All rights reserved.
//
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int k, i, n, m, dinamicaA[2000001], dinamicaB[2000001], pozitii[2000001], k2;
char a[2000001],b[2000001];
vector<int> positions;
int main()
{
fin >> (a+1);
n = strlen(a+1);
fin >> (b+1);
m = strlen(b+1);
k=0;
for(i=2; i <= n; ++i)
{
while (k && a[k+1] != a[i])
k = dinamicaA[k];
if (a[k+1] == a[i])
++k;
dinamicaA[i] = k;
}
k = 0; k2 = 0;
for (i=1; i <= m; ++i)
{
while (b[i] != a[k+1] && k)
k = dinamicaA[k];
if (b[i] == a[k+1])
{
++k;
if(k==n)
pozitii[++k2] = i;
}
dinamicaB[i] = k;
}
fout << k2 << "\n";
k2 = min(1000,k2);
for(i = 1; i <= k2; ++i)
fout << pozitii[i] - n << " ";
return 0;
}