Pagini recente » Cod sursa (job #130416) | Cod sursa (job #2863010) | Cod sursa (job #2876074) | Cod sursa (job #125128) | Cod sursa (job #1781582)
//
// 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");
long long k, i, n, dinamicaA[2000001], dinamicaB[2000001];
string a,b;
vector<long long> positions;
int main()
{
fin >> a >> b;
k=0;
dinamicaA[0] = 0;
for(i=1; i<a.size(); ++i)
{
while (k && a[k] != a[i])
k = dinamicaA[k];
if (a[k] == a[i])
++k;
dinamicaA[i] = k;
}
k = 0;
for (i=0; i < b.size(); ++i)
{
while (b[i] != a[k] && k)
{
k = dinamicaA[k-1];
}
if (b[i] == a[k])
{
++k;
if(k==a.size())
{
positions.push_back(i);
if(positions.size()==1000)
break;
}
}
dinamicaB[i] = k;
}
fout << positions.size() << "\n";
for(i = 0; i < positions.size(); ++i)
{
fout << positions[i] - a.size() + 1 << " ";
}
return 0;
}