Pagini recente » Cod sursa (job #3288863) | Cod sursa (job #694091) | Cod sursa (job #1424874) | Cod sursa (job #1350830) | Cod sursa (job #2433850)
#include<iostream>
#include<string>
#include<fstream>
#include<vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
void compute_lsp(int*lsp_array,string to_compute)
{
int i=1,l=0;
lsp_array[0]=0;
while(i<to_compute.length())
{
if(to_compute[i]==to_compute[l])
{
l++;
lsp_array[i]=l;
i++;
}
else
{
if(l!=0)
{
l=lsp_array[l-1];
}
else
{
lsp_array[i]=0;
i++;
}
}
}
}
vector<int> kmp(string main,string pattern)
{
vector<int> to_return;
int lsp[pattern.length()];
compute_lsp(lsp,pattern);
int i=0,p=0;
while(i<main.length())
{
if(main[i]==pattern[p])
{
i++;
p++;
}
if(p==pattern.length())
{
to_return.push_back(i-p);
p=lsp[p-1];
}
if(i<main.length() &&main[i]!=pattern[p])
{
if(p!=0)
{
p=lsp[p-1];
}
else
i++;
}
}
return to_return;
}
int main()
{
string a,b;
in>>a>>b;
vector<int> results=kmp(b,a);
out<<results.size()<<'\n';
for(int i=0; i<results.size(); i++)
out<<results[i]<<' ';
return 0;
}