Pagini recente » Istoria paginii runda/3333333333333 | Cod sursa (job #2699340) | Cod sursa (job #2892712) | Cod sursa (job #2937498) | Cod sursa (job #2862366)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000000;
int aux[NMAX];
vector <int> a;
int main()
{
string s,pat;
fin>>pat>>s;
//acum trebuie sa cream vectorul auxiliar special de poz
aux[0] = 0;
int i = 0,j = 1;
while(j < pat.size())
{
if(pat[i] == pat[j])
{
aux[j] = i + 1;
i++;
j++;
}
else if(i == 0)
{
j++;
aux[j] = 0;
}
else
{
i = aux[i - 1];
}
}
i = 0,j = 0;
int ans = 0;
while(i < s.size())
{
if(pat[j] == s[i])
{
j++;
i++;
}
if(j == pat.size())
{
ans++;
a.push_back(i - j);
}
if(s[i] != pat[j])
{
if(j != 0)
j = aux[j - 1];
else
i++;
}
}
fout<<ans<<"\n";
int lim = a.size();
lim = min(lim,1000);
for(int i = 0;i <lim;i++)
fout<<a[i]<<" ";
return 0;
}