Pagini recente » Cod sursa (job #1929395) | Cod sursa (job #2882105) | Cod sursa (job #1461173) | Cod sursa (job #2701709) | Cod sursa (job #729261)
Cod sursa(job #729261)
#include <string>
#include <vector>
#include <fstream>
using namespace std;
#define MAX_STR 2000000
void read(string & a, string & b)
{
a.reserve(MAX_STR);
b.reserve(MAX_STR);
ifstream f("strmatch.in");
f>>a>>b;
}
void write(const vector<int> & res)
{
ofstream f("strmatch.out");
size_t n = res.size();
f<<n<<'\n';
for (size_t i=0; i<n; i++)
f<<res[i]<<' ';
}
void solve(const string & a, const string & b, vector<int> & res)
{
res.reserve(1024);
size_t sa = a.size();
size_t sb = b.size();
vector<int> t;
t.reserve(sa+1);
t.push_back(-1);
t.push_back(0);
size_t cand = 0;
for (size_t i = 2; i<=sa;)
{
if (a[cand] == a[i-1])
{
t.push_back(t[i-1]+1);
i++; cand++;
} else {
if (cand)
cand = t[cand];
else {
t.push_back(0);
i++;
}
}
}
size_t i,m;
for (m = 0, i = 0; m+i < sb;)
{
if (i < sa && a[i] == b[i+m])
{
i++;
if (i==sa)
res.push_back(m);
} else {
m = m + i - t[i];
if (t[i] >= 0)
i = t[i];
else
i = 0;
}
}
}
int main()
{
string a,b;
vector<int> results;
read(a,b);
solve(a,b,results);
write(results);
return 0;
}