Pagini recente » Cod sursa (job #3231638) | Cod sursa (job #875681) | Cod sursa (job #650414) | Cod sursa (job #1149611) | Cod sursa (job #2366166)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int vector_ajutator[2000005], l;
char pattern[2000005], sir_mare[2000005];
vector<int>rasp;
void creeare_vector_ajutator()
{
int i=0, j=1;
vector_ajutator[0]=0;
while (j<l)
{
if (pattern[i]==pattern[j])
{
vector_ajutator[j]=i+1;
++i;
++j;
}
else
{
if (i==0)
{
vector_ajutator[j]=0;
++j;
}
else
{
i=vector_ajutator[i-1];
}
}
}
}
void comparare()
{
int l_mare=strlen(sir_mare);
int ind_sir=0, ind_pattern=0;
while (ind_sir<l_mare)
{
if (sir_mare[ind_sir]==pattern[ind_pattern])
{
++ind_pattern;
if (ind_pattern==l)
{
rasp.push_back(ind_sir-l+1);
ind_pattern=vector_ajutator[ind_pattern-1];
}
}
else
{
if (ind_pattern==0)
ind_pattern=0;
else{
ind_pattern=vector_ajutator[ind_pattern-1];
}
}
++ind_sir;
}
g << rasp.size() << '\n';
for (auto &v:rasp)
{
g << v <<' ';
}
}
int main()
{
f >> pattern;
l=strlen(pattern);
creeare_vector_ajutator();
f >> sir_mare;
comparare();
return 0;
}