Pagini recente » Cod sursa (job #887704) | Cod sursa (job #2604622) | Cod sursa (job #3004859) | Cod sursa (job #1051216) | Cod sursa (job #1974676)
#include<fstream>
#include<vector>
#include<string>
#define modulo 666013
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000005;
string a, b;
int i, n, k, j,contor,st,dr,x,y;
int prefix[NMAX];
vector<int> sol;
void build_prefix()
{
prefix[0] = 0;
int k = -1;
for(int i = 1; i < a.length(); i++)
{
while(k > 0 && a[k + 1] != a[i])
{
k = prefix[k];
}
if(a[k + 1] == a[i])
{
k++;
}
prefix[i] = k;
}
for(i = 0; i < a.length(); i++)
{
//fout << prefix[i] << " ";
}
}
int main()
{
fin >> a >> b;
//fout << a <<"\n"<<b <<"\n";
build_prefix();
int m = a.length();
int k = -1;
for(int i = 1; i < b.length(); i++)
{
while(k > 0 && a[k + 1] != b[i])
{
k = prefix[k];
}
if(a[k + 1] == b[i])
{
k++;
}
if(k == m - 1)
{
//fout << i - m + 1 << "\n";
sol.push_back(i - m + 1);
k = prefix[k];
}
prefix[i] = k;
}
if(sol.size() > 1000 ) contor = 1000;
else contor = sol.size();
fout << sol.size() << "\n";
for(i = 0; i < contor;i++)
{
fout << sol[i] <<" ";
}
}