Pagini recente » Cod sursa (job #1971822) | Cod sursa (job #1654363) | Cod sursa (job #1490574) | Cod sursa (job #2611349) | Cod sursa (job #2453382)
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#define fs first
#define sc second
#define pii pair <int, int>
#define Nmax 2000005
#define MOD1 666013
#define MOD2 100007
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[Nmax], b[Nmax];
int pr[Nmax], ans;
vector <int> sol;
void prefix(char s[], int len)
{
int j=0;
for (int i = 2; i <= len; i++)
{
while (j!=0 && s[i]!=s[j+1]) j = pr[j];
if (s[i] == s[j+1]) j++;
pr[i]=j;
}
}
int main()
{
f >> (a+1) >> (b+1);
int la=strlen(a+1), lb=strlen(b+1);
prefix(a, la);
int j=0;
for (int i = 1; i <= lb; i++)
{
while (j!=0 && b[i]!=a[j+1]) j = pr[j];
if (b[i] == a[j+1]) j++;
if (j == la)
{
ans++;
if (sol.size()<1000) sol.push_back(i-la);
}
}
g << ans << '\n';
for (auto i:sol) g << i << " ";
return 0;
}