Pagini recente » Cod sursa (job #3200297) | Cod sursa (job #283081) | Cod sursa (job #754777) | Cod sursa (job #198825) | Cod sursa (job #2447395)
#include <bits/stdc++.h>
#define maxim 2000003
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int dp[maxim];
int main()
{
string a, b;
f >> a >> b;
int len = a.size();
a += '*';
a+= b;
vector <int> id;
int ans = 0;
dp[0] = -1;
for (int i = 1; i < a.size(); ++ i)
{
int j = i - 1;
while (dp[j] != -1 && a[i] != a[dp[j] + 1])
j = dp[j];
dp[i] = dp[j];
if (a[i] == a[dp[j] + 1])
dp[i] = dp[j] + 1;
if (dp[i] + 1 == len)
{
ans ++;
if (ans <= 1000)
id.push_back(i - 2 * len);
}
}
g << ans <<'\n';
for (auto i : id)
g << i << " ";
}