Pagini recente » Istoria paginii runda/oni_2015_zi1/clasament | Istoria paginii runda/rar13/clasament | Istoria paginii runda/rar18/clasament | Cod sursa (job #2104984) | Cod sursa (job #2862364)
#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 = min(a.size(),1000)
for(int i = 0;i <lim;i++)
fout<<a[i]<<" ";
return 0;
}