Pagini recente » Cod sursa (job #2959823) | Cod sursa (job #1088277) | Cod sursa (job #1415055) | Cod sursa (job #2461967) | Cod sursa (job #2372426)
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
const string file = "strmatch";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647;
int n, m, prv[2000005];
string s1, s2;
int main()
{
ifstream fin (file+".in");
ofstream fout (file+".out");
fin >> s1 >> s2;
n = s1.length(), m = s2.length();
prv[0] = 0;
int k = 0;
for (int i = 1; i < n; ++i){
while(k > 0 && s1[k] != s1[i])
k = prv[k-1];
if(s1[k] == s1[i])
++k;
prv[i] = k;
}
int sol = 0;
vector<int> ans;
k = 0;
for (int i = 0; i < m; ++i){
while(k > 0 && s1[k] != s2[i])
k = prv[k-1];
if(s1[k] == s2[i])
++k;
if(k == n){
++sol;
if(sol <= 1000)
ans.push_back(i-n+1);
}
}
fout << sol << "\n";
for (auto x : ans)
fout << x << " ";
fout << "\n";
return 0;
}