Pagini recente » Cod sursa (job #2563516) | Cod sursa (job #2350545) | Cod sursa (job #173259) | Cod sursa (job #2006107) | Cod sursa (job #3032314)
#include <vector>
#include <fstream>
#include <string.h>
using namespace std;
#define MAX_N 2000005
char v[MAX_N], sir[MAX_N];
int pi[MAX_N];
vector <int> ans;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
int main()
{
int x, i;
in >> (v + 1);
int n = strlen(v + 1);
for(i = 2; i <= n; ++i)
{
x = pi[i-1];
while(v[x + 1] != v[i] && x != 0)
x = pi[x];
if(v[x + 1] == v[i])
pi[i] = x + 1;
else
pi[i] = 0;
}
in >> (sir + 1);
int m = strlen(sir + 1);
//while(cin >> sir[++m]);
int j = 1;
while(j <= m)
{
if(v[i] == sir[j])
{
if(i == n)
{
ans.push_back(j - i);
j -= ( (pi[i] == i - 1) ? pi[i] - 1 : pi[i] );
i = 1;
} else
{
i++;
j++;
}
} else
{
j -= ( (pi[i] == i - 1) ? pi[i] - 1 : pi[i] );
i = 1;
}
}
out << ans.size() << '\n';
for(auto x : ans)
out << x << " ";
return 0;
}