Pagini recente » Cod sursa (job #306550) | Cod sursa (job #2628546) | Cod sursa (job #1987645) | Cod sursa (job #2019044) | Cod sursa (job #2060746)
#include<fstream>
#include<vector>
using namespace std;
string a, b;
vector<int> sol;
int poz[2000005];
string x;
bool bo;
/*void a_precalc()
{
int i = 0;
int j = 1;
for(; j < a.size(); j++)
{
while(i != 0 && a[i] != a[j])
{
i = poz[i - 1];
}
if(a[i] == a[j])
i++;
poz[j] = i;
}
}*/
void a_precalc()
{
int i = 0;
int j = 1;
for(; j < a.size(); )
{
while(i != 0 && a[i] != a[j])
{
i = poz[i - 1];
}
if(a[i] == a[j])
{
poz[j] = i + 1;
i++;
j++;
}else
{
poz[j] = i;
j++;
}
}
}
void str_match()
{
int i = 0;
int j = 0;
while(j < b.size())
{
while(i != 0 && a[i] != b[j])
{
i = poz[i - 1];
}
if(a[i] == b[j])
{
i++;
j++;
if(i == a.size())
{
sol.push_back(j - i);
i = poz[i - 1];
}
}else
{
j++;
}
}
}
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main()
{
in >> a;
in >> b;
a_precalc();
str_match();
out << sol.size() << "\n";
int x = sol.size();
for(int i = 0; i < min(1000, x); i++)
{
out << sol[i] << " ";
}
return 0;
}