Pagini recente » Cod sursa (job #1625267) | Cod sursa (job #529642) | Cod sursa (job #2378102) | Cod sursa (job #1494170) | Cod sursa (job #2397027)
#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 Pattern()
{
int last = 0;
lps[0] = 0;
for(int i = 1; i < P.size(); ++i)
if(P[i] == P[last])
{
last++;
lps[i] = last;
}
else
{
if( last )
{
last = lps[last - 1];
i--;
}
}
//for(int i = 0; i < P.size(); ++i) fout << lps[i] << ' ';
}
void Do()
{
fin >> P >> T;
Pattern();
int j = 0, i = 0;
while(i < T.size())
{
if(T[i] == P[j])
{
i++;j++;
}
if(j == P.size())
{
Pos.push_back( i - j );
j = lps[j-1];
}
else
if(i < T.size() && T[i] != P[j])
{
if( j )
j = lps[j - 1];
else i++;
}
}
fout << Pos.size() << '\n';
for(int i = 0; i < Pos.size() && i < 1000; ++i)
fout << Pos[i] << ' ';
}
int main()
{
Do();
return 0;
}