Pagini recente » Cod sursa (job #1324585) | Cod sursa (job #3138077) | Cod sursa (job #3285122) | Cod sursa (job #2781377) | Cod sursa (job #1764119)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
void kmp_table(string& w,vector<int>& t)
{
t.resize(w.size()+1);
int pos = 2,cnd = 0;
t[0] = -1,t[1] = 0;
while(pos <= w.size())
{
if(w[pos-1] == w[cnd])
{
t[pos] = cnd+1;
cnd++;
pos++;
}
else if(cnd>0)
cnd = t[cnd];
else
{
t[pos] = 0;
pos++;
}
}
//for(int i = 0 ; i < t.size() ; i++)
// cout<<"i :"<<i<<" t["<<i<<"] :"<<t[i]<<"\n";
}
int main()
{
vector<int> pos;
string s,w;
in >> w >> s;
int m = 0 , i = 0;
vector<int> t;
cout<<w<<"\n"<<s;
kmp_table(w,t);
while( m + i <s.size() )
{
if(w[i] == s[m+i])
{
if(i == w.size()-1)
pos.push_back(m);
i++;
}
else
if(t[i] > -1)
m = m + i - t[i],i = t[i];
else
m++ , i = 0;
}
out<<pos.size()<<'\n';
for(int j = 0 ; j < std::min((int)pos.size(),1000); j++)
out<<pos[j]<<" ";
return 0;
}