Pagini recente » Cod sursa (job #1335185) | Cod sursa (job #1072069) | Cod sursa (job #2097205) | Cod sursa (job #138847) | Cod sursa (job #2396340)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000001;
string P, T;
vector <int> Pos;
int lps[NMAX];
void Precalc()
{
for(int i = 1; i < P.size(); ++i)
if(P[lps[i-1]] == P[i])lps[i] = lps[i-1] + 1;
}
void Read()
{
fin >> P >> T;
Precalc();
int i, j;
i = j = 0;
for(int i = 0; i < T.size(); ++i)
{
if(T[i] == P[j])
{
if(j == P.size() - 1)
{
Pos.push_back(i);
j = lps[j-1];
}
j++;
}
else j = lps[j-1];
}
fout << Pos.size() << '\n';
for(int i = 0; i < Pos.size(); ++i)
fout << Pos[i] - P.size() + 1<< ' ';
}
int main()
{
Read();
return 0;
}