Pagini recente » Cod sursa (job #3207233) | Cod sursa (job #1169771) | Cod sursa (job #2834910) | Cod sursa (job #590453) | Cod sursa (job #1974694)
#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,m;
int prefix[NMAX];
vector<int> sol;
void build_prefix()
{
prefix[1] = 0;
int k = 0;
for(int i = 2; i <= n; 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;
n = a.length();
m = b.length();
a = ' ' + a;
b = ' ' + b;
//fout << a <<"\n"<<b <<"\n";
build_prefix();
int k = 0;
for(int i = 1; i <= m; i++)
{
while(k > 0 && a[k + 1] != b[i])
{
k = prefix[k];
}
if(a[k + 1] == b[i])
{
k++;
}
if(k == n)
{
//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] <<" ";
}
}