Pagini recente » Cod sursa (job #2150949) | Cod sursa (job #1465271) | Cod sursa (job #720080) | Cod sursa (job #2284374) | Cod sursa (job #2321810)
#include <bits/stdc++.h>
using namespace std;
string s, p;
int n, m, i, j, l[2000005], v[1005], k;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> p >> s;
n = p.size();
m = s.size();
j = 0;
for(i = 1; i <= n; i ++)
{
while(j > 0 && p[j] != p[i])j = l[j - 1];
if(p[j] == p[i])j++;
l[i] = j;
}
j = 0;
for(i = 0; i <= m; i ++)
{
while(j > 0 && p[j] != s[i])j = l[j - 1];
if(p[j] == s[i])j++;
if(j == n)
{
j = l[n - 1];
if(n < 1000)v[++k] = i - n + 1;
}
}
g << k << "\n";
for(i = 1; i <= min(k, 1000); i ++)
g << v[i] << " ";
return 0;
}