Pagini recente » Cod sursa (job #1241332) | Cod sursa (job #411764) | Monitorul de evaluare | Cod sursa (job #908562) | Cod sursa (job #3311068)
#include <bits/stdc++.h>
#define NMAX 2000001
#define POZ_MAX 1000
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int pi[NMAX]; ///pi[i] = lungimea maxima a unui prefix al sirului format din primele i caractere ale lui a care este si sufix
int pozitii[POZ_MAX]; ///pozitiile in care sirul a se potriveste peste sirul b
int main()
{
string a, b;
in >> a >> b;
int n=a.size(), m=b.size();
int l_prefix=0; ///lungimea unui prefix
pi[0]=l_prefix;
for(int i=1; i<n; i++)
{
while(l_prefix>0 && a[l_prefix]!=a[i]) ///cat timp nu am gasit o potrivire
{
l_prefix=pi[l_prefix-1];
}
if(a[l_prefix]==a[i]) ///daca am gasit o potrivire
{
l_prefix++;
}
pi[i]=l_prefix;
}
l_prefix=0;
int nr_aparitii=0; ///numarul de aparitii ale lui a in b
for(int j=0; j<m; j++)
{
while(l_prefix>0 && a[l_prefix]!=b[j]) ///cat timp nu am gasit o potrivire
{
l_prefix=pi[l_prefix-1];
}
if(a[l_prefix]==b[j]) ///daca caracterele se potrivesc
{
l_prefix++;
if(l_prefix==n) ///daca am ajuns la finalul sirului a
{
if(nr_aparitii<POZ_MAX)
pozitii[nr_aparitii]=j-n+1; ///adaugam pozitia de inceput a sirului la vectorul de pozitii
nr_aparitii++; ///marim numarul de aparitii
}
}
}
out << nr_aparitii << "\n";
for(int poz=0; poz<POZ_MAX; poz++) ///afisam pozitiile
{
out << pozitii[poz] << " ";
}
return 0;
}