Pagini recente » Monitorul de evaluare | Cod sursa (job #878728) | Cod sursa (job #1846051) | Cod sursa (job #271630) | Cod sursa (job #1279862)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
string a,b;
int tbl[2000001];
vector<int> solutii;
void potrivire()
{
tbl[0]=-1;
int k=-1,i;
for (i=1;i<a.size();i++)
{
if (a[k+1]==a[i])
{
k++;
}
else while (k>-1&&a[k]!=a[i])
{
k=tbl[k];
}
tbl[i]=k;
}
}
void rezolvare()
{
int i,k=0;
for (i=0;i<b.size();i++)
{
while(k>=0&&a[k+1]!=b[i])
{
k=tbl[k];
}
if (a[k+1]==b[i])
{
k++;
}
if (k==a.size()-1){solutii.push_back(i-k);}
}
}
void afisare()
{
ofstream out("strnatch.out");
int i;
out<<solutii.size();
out<<"\n";
for (i=0;i<solutii.size();i++)
{
out<<solutii[i]<<" ";
}
}
int main()
{
ifstream in("strmatch.in");
in>>a;
in>>b;
potrivire();
rezolvare();
afisare();
}