Pagini recente » Cod sursa (job #396978) | Cod sursa (job #972484) | Cod sursa (job #827019) | Cod sursa (job #125578) | Cod sursa (job #753450)
Cod sursa(job #753450)
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
#define min(a,b) (((a) > (b)) ? (a) : (b) )
void form_t(vector <int> & t,string s)
{
int i,pos = 0;
for(i=1;i<t.size();++i)
{
t[i] = pos;
if(s[i] == s[pos])
++pos;
else
pos = 0;
}
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
in >> a >> b;
vector <int> t (a.length(),0);
vector <int> f ;
form_t(t,a);
int i = 0,pos = 0;
long long unsigned int n = 0;
while(i < b.size())
{
if(pos == 0)
{
while(b[i] != a[0] && i < b.size())
++i;
}
while(b[i] == a[pos] && i < b.size() && pos < a.size())
{
++i;
++pos;
}
if(pos == a.size())
{
if(n<1000)
f.push_back(i-pos);
pos = t[pos-1] + 1;
++n;
}
else
pos = t[pos];
}
out <<n<< "\n";
for(i=0;i<min(f.size(),1000);++i)
out << f[i]<< " ";
return 0;
}