Pagini recente » Cod sursa (job #2149238) | Istoria paginii utilizator/maleticimiroslav | Istoria paginii runda/ada32/clasament | Cod sursa (job #1277375) | Cod sursa (job #2321881)
#include <bits/stdc++.h>
using namespace std;
char s[2000005], p[2000005];
int n, m, i, j, l[2000005], v[1005], nr_sol;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> p >> s;
n = strlen(p);
m = strlen(s);
for(i = n; i > 0; i --)
p[i] = p[i - 1];
for(i = m; i > 0; i --)
s[i] = s[i - 1];
for(i = 2; i <= n; i ++)
{
while(j > 0 && p[i] != p[j + 1])j = l[j];
if(p[i] == p[j + 1])j++;
l[i] = j;
}
j = 0;
for(i = 1; i <= m; i ++)
{
while(j > 0 && s[i] != p[j + 1])j = l[j];
if(s[i] == p[j + 1])j++;
if(j == n)v[++nr_sol] = i - n, j = l[j];
}
g << nr_sol << "\n";
for(i = 1; i <= min(nr_sol, 1000); i ++)
g << v[i] << " ";
return 0;
}