Pagini recente » Cod sursa (job #124870) | monthly-2012/runda-8/solutii | Cod sursa (job #3166845) | Cod sursa (job #1926353) | Cod sursa (job #753438)
Cod sursa(job #753438)
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
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;
getline(in,a);
getline(in,b);
vector <int> t (a.length(),0);
vector <int> f ;
form_t(t,a);
int i = 0,pos = 0;
while(i < b.size() && f.size() < 1000)
{
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())
{
f.push_back(i-pos);
pos = t[pos-1] + 1;
}
else
pos = t[pos];
}
out << f.size() << "\n";
for(i=0;i<f.size();++i)
out << f[i]<< " ";
return 0;
}